仿照美国州际公路建设者，牛们引入牧场间道路编号系统。已将 $N$ 片牧场（$2\le N\le25$）编号 $1\ldots N$，现在每条两牧场间道路都有不同的 $1\ldots2000$ 编号，如 I-9、I-16。

例如牧场 1、2、3、4 由 I-3、I-6、I-9、I-16 相连：

                  4--<I-6>--2
                 /         /
             <I-16>     <I-9>   
               /         /
              1--<I-3>--3

Bessie 喜欢沿新系统从牧场 1 步行到 2，每次不重复访问同一牧场，图中可走 1-4-2、1-3-2。

多年练出了惊人数学本领，爱在每次步行求途经道路编号最大公因数（GCF）。1-4-2 经 I-16、I-6，GCF 为 2，因为 2 整除 16、6，没更大整数可以。

日复一日她走遍 1 到 2 所有可能路线，记每个 GCF。全部各走一次后求这些值的最小公倍数（LCM）。例中 GCF 为 2、3：$\gcd(6,16)=2$、$\gcd(3,9)=3$，LCM 为 6。

大路网可能走得累，但仍想知道每张图的 LCM，请替她计算。

输入格式

• 第 1 行：$N$。
• 第 $2..N+1$ 行：$N$ 行对称连接矩阵。第 $L$ 行的 $N$ 个空格分隔整数表示牧场 $L-1$ 与其他牧场连接。首整数为 $L-1$ 与 1 间道路编号，第二个为与 2 的编号，依此类推。$A$ 连 $B$ 则 $B$ 连 $A$；无道路用 0。

输出格式

一行一个整数，1 到 2 全部可能步行的 GCF 的 LCM。保证答案最多 100 位。

样例

输入格式 1

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

输出格式 1

6

题目作者：Vlad Novakovski，2002