Ispirate ai costruttori delle autostrade interstatali USA, le mucche numerano strade tra pascoli. $N$ pascoli ($2\le N\le25$) sono $1\ldots N$, ogni strada numero distinto $1\ldots2000$, come I-9 e I-16.

Esempio: pascoli 1,2,3,4 uniti da I-3,I-6,I-9,I-16:

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

Bessie ama camminare da 1 a 2 nel nuovo sistema, senza rivisitare un pascolo: 1-4-2 e 1-3-2 nell’esempio.

Negli anni sviluppò talento matematico straordinario e cerca massimo comune divisore (GCF) dei numeri percorsi. 1-4-2 usa I-16,I-6, GCF 2: 2 divide 16 e 6, nessun intero maggiore entrambi.

Giorno dopo giorno percorre tutte le rotte $1\to2$ ricordando GCF. Dopo aver percorso tutte le rotte una volta ciascuna calcola minimo comune multiplo (LCM). Esempio 2,3: $\gcd(6,16)=2$, $\gcd(3,9)=3$, LCM 6.

Reti grandi la stancano, ma vuole LCM di ogni mappa. Calcolalo.

Input

• Riga 1: $N$.
• Righe $2..N+1$: $N$ righe matrice simmetrica. Riga $L$: $N$ interi per spazi, collegamenti di $L-1$, primo numero strada a 1, secondo a 2, ecc. $A$ a $B$ implica inverso. Senza strada, 0.

Output

Una riga, intero LCM dei GCF di tutte le passeggiate $1\to2$, garantito massimo 100 cifre.

Esempi

Input 1

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

Output 1

6

Autore: Vlad Novakovski, 2002