Wzorując się na budowniczych autostrad międzystanowych USA, krowy numerują drogi pastwisk. $N$ pastwisk ($2\le N\le25$) ma $1\ldots N$, każda droga odrębny numer $1\ldots2000$, np. I-9 i I-16.

Przykład: pastwiska 1,2,3,4 łączą I-3,I-6,I-9,I-16:

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

Bessie lubi spacerować z 1 do 2 nowym systemem, bez powtarzania pastwiska: 1-4-2 i 1-3-2 w przykładzie.

Przez lata rozwinęła niesamowitą matematykę i szuka największego wspólnego dzielnika (GCF) numerów dróg. 1-4-2 używa I-16,I-6, GCF 2: 2 dzieli 16 i 6, żaden większy całkowity obu.

Codziennie przechodzi wszystkie trasy $1\to2$ i pamięta GCF. Po przejściu wszystkich możliwych tras po jednym razie oblicza najmniejszą wspólną wielokrotność (LCM). Przykład 2,3: $\gcd(6,16)=2$, $\gcd(3,9)=3$, LCM 6.

Duże sieci męczą, ale chce LCM każdej mapy. Oblicz.

Wejście

• Wiersz 1: $N$.
• Wiersze $2..N+1$: $N$ wierszy symetrycznej macierzy. Wiersz $L$: $N$ całkowitych ze spacjami, połączenia $L-1$, pierwszy numer do 1, drugi do 2 itd. $A$ z $B$ oznacza odwrotność. Brak drogi — 0.

Wyjście

Jeden wiersz, całkowite LCM wszystkich GCF spacerów $1\to2$, gwarantowane do 100 cyfr.

Przykład

Wejście 1

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

Wyjście 1

6

Autor: Vlad Novakovski, 2002