Inspiradas por las autopistas interestatales de EE. UU., las vacas numeran caminos entre pastos. $N$ pastos ($2\le N\le25$) numerados $1\ldots N$, cada camino con número único $1\ldots2000$, como I-9 e I-16.

Ejemplo: pastos 1,2,3,4 unidos por I-3,I-6,I-9,I-16:

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

Bessie camina de 1 a 2 por el nuevo sistema, sin repetir pasto: 1-4-2 y 1-3-2 en el ejemplo.

Durante años desarrolló asombroso talento matemático y halla máximo común divisor (GCF) de números recorridos. 1-4-2 usa I-16,I-6, GCF 2: 2 divide 16 y 6, ninguno mayor divide ambos.

Día tras día recorre todas las rutas $1\to2$ y recuerda GCF. Tras recorrer todas las rutas una vez cada una, calcula mínimo común múltiplo (LCM). Ejemplo 2,3: $\gcd(6,16)=2$, $\gcd(3,9)=3$, LCM 6.

En redes grandes se cansa, pero quiere LCM de cada mapa. Calcúlalo.

Entrada

• Línea 1: $N$.
• Líneas $2..N+1$: $N$ líneas de matriz simétrica. Línea $L$: $N$ enteros separados por espacios, conexiones de $L-1$, primero número a 1, segundo a 2, etc. $A$ con $B$ implica inversa. Sin camino, 0.

Salida

Una línea, entero LCM de GCF de todos los paseos $1\to2$, hasta 100 dígitos garantizados.

Ejemplos

Entrada 1

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

Salida 1

6

Autor: Vlad Novakovski, 2002