米国州間高速道路の建設者に倣い、牛は牧場間道路番号制度を導入しました。$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\to2$ 経路の 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$ と各牧場の接続、最初は 1、二番目は 2 への道路番号、以下同様。$A$ と $B$ は双方向で、道路なしは 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