仿照美國州際公路建造者，牛引入牧場間道路編號系統。$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）。例中 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