Description
Taking their cue from the builders of the USA's Interstate Highway system, the cows have introduced the Interpasture Path numbering system. They have already numbered the N (2 <= N <= 25) pastures with the integers 1..N and now are numbering each path between two pastures with its own distinct Interpasture Path number in the range 1..2000
(e.g., I-9 and I-16).
In an example Interpasture Path map, four pastures numbered 1, 2, 3, and 4 are connected by Interpasture Paths I-3, I-6, I-9, and I-16:
4--< I-6>--2
/ /
< I-16> < I-9>
/ /
1--< I-3>--3
Bessie likes to walk from pasture 1 to pasture 2 on the nifty new Interpasture system. During each walk, she never visits the same pasture twice, so possible walks on the sample map above are 1-4-2 and 1-3-2.
Over the years, Bessie has developed an amazing mathematical skill that she likes to exercise. During each walk, she enjoys finding the greatest common factor (GCF) of the Interpasture Paths that she traverses. For instance, the walk designated 1-4-2 touches I-16 and I-6 which have the greatest common factor of 2 (since 2 properly divides into 16 and 6 but no larger integer does).
As she walks the pastures day after day, she takes all the possible routes from pasture 1 to pasture 2 and remembers each of the GCFs. After she has taken every possible walk once, she computes the least common multiple (LCM) of all the GCFs. For this example, the two GCF values are 2 and 3 (GCF(6,16)=2 and GCF(3,9)=3), so the LCM is 6.
For large networks of paths, Bessie might get tired of all the walking, but she really wants to know the LCM for every map. Calculate that number for her.
Input
Line 1: N
Lines 2..N+1: These N lines represent the symmetric Interpasture Path connectivity matrix of the pastures. Line L shows the connectivity between pasture L-1 and the other pastures with its N space-separated integers. The first integer on each line is the Interpasture Path number that connects pasture L-1 and and pasture 1; the second integer is the IP number connecting pasture L-1 and pasture 2; etc. If pasture A connects to pasture B, then pasture B connects to Pasture A. When no Interpasture Path is available, the integer is 0.
Output
A single line with a single integer that is the LCM of the GCFs of all the possible walks from pasture 1 to pasture 2. It is guaranteed that the answer will contain 100 or fewer digits.
Sample Input
4
0 0 3 16
0 0 9 6
3 9 0 0
16 6 0 0
Sample Output
6
