Cow Math

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.

PROBLEM NAME: cowmath

INPUT FORMAT:

* 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.  When no
Interpasture Path is available, the integer is 0.

SAMPLE INPUT:

4
0 0 3 16
0 0 9 6
3 9 0 0
16 6 0 0

OUTPUT FORMAT:

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 OUTPUT:

6