Inspiradas pelos construtores das rodovias interestaduais dos EUA, as vacas numeram caminhos entre pastos. $N$ pastos ($2\le N\le25$) são $1\ldots N$, cada caminho número distinto $1\ldots2000$, como I-9 e I-16.

Exemplo: pastos 1,2,3,4 ligados por I-3,I-6,I-9,I-16:

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

Bessie gosta de andar de 1 a 2 no novo sistema, sem visitar pasto duas vezes: 1-4-2 e 1-3-2 no exemplo.

Ao longo dos anos ganhou talento matemático incrível e calcula máximo divisor comum (GCF) dos números percorridos. 1-4-2 usa I-16,I-6, GCF 2: 2 divide 16 e 6, nenhum inteiro maior divide ambos.

Dia após dia anda todas as rotas $1\to2$ e lembra GCF. Após percorrer todas as rotas uma vez cada, calcula mínimo múltiplo comum (LCM). Exemplo 2,3: $\gcd(6,16)=2$, $\gcd(3,9)=3$, LCM 6.

Redes grandes cansam, mas quer LCM de todo mapa. Calcule.

Entrada

• Linha 1: $N$.
• Linhas $2..N+1$: $N$ linhas de matriz simétrica. Linha $L$: $N$ inteiros por espaços, conexões de $L-1$, primeiro número para 1, segundo para 2, etc. $A$ com $B$ implica inversa. Sem caminho, 0.

Saída

Uma linha, inteiro LCM dos GCF de todos os passeios $1\to2$, garantidos até 100 dígitos.

Exemplos

Entrada 1

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

Saída 1

6

Autor: Vlad Novakovski, 2002