问题重述

奶牛们模仿美国州际公路系统的建设者，引入了“Interpasture Path”编号系统。他们已经将 $N$（$2 \leq N \leq 25$）个牧场编号为 1 到 $N$，并为连接两个牧场的每条路径分配了一个唯一的编号，范围在 1 到 2000 之间（例如 I-9 和 I-16）。

给定一个牧场和路径的连通图，贝茜喜欢从牧场 1 走到牧场 2，且不重复访问任何牧场。对于每条可能的路径，她会计算所经过路径编号的最大公约数（GCF）。最后，她会将所有路径的 GCF 的最小公倍数（LCM）计算出来。

输入格式

• 第一行：$N$（牧场数量）
• 接下来的 $N$ 行：表示牧场的对称连通矩阵。第 $L$ 行表示牧场 $L-1$ 与其他牧场的连接情况，其中第 $i$ 个数字表示连接牧场 $L-1$ 和牧场 $i$ 的路径编号（0 表示没有路径）。

输出格式

• 一行：所有可能路径的 GCF 的 LCM。

示例输入

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

示例输出

6