Inspirées des constructeurs des autoroutes inter-États américaines, les vaches numérotent les chemins interpâturages. $N$ pâturages ($2\le N\le25$) sont $1\ldots N$ ; chaque chemin a un numéro distinct $1\ldots2000$, tel I-9 ou I-16.

Exemple : pâturages 1,2,3,4 reliés par I-3,I-6,I-9,I-16 :

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

Bessie aime marcher de 1 à 2 sur ce nouveau système, sans revisiter un pâturage : 1-4-2 et 1-3-2 dans l’exemple.

Au fil des ans elle a développé un talent mathématique étonnant, et calcule le plus grand diviseur commun (GCF) des numéros parcourus. 1-4-2 passe I-16 et I-6, GCF 2 : 2 divise 16 et 6, aucun entier plus grand ne le fait.

Chaque jour elle parcourt tous les itinéraires $1\to2$ et mémorise leurs GCF. Après avoir parcouru chacun une fois, elle calcule leur plus petit multiple commun (LCM). Exemple : 2,3, $\gcd(6,16)=2$, $\gcd(3,9)=3$, LCM 6.

Sur de grands réseaux elle se fatigue, mais veut le LCM de chaque carte. Calculez-le.

Entrée

• Ligne 1 : $N$.
• Lignes $2..N+1$ : $N$ lignes de matrice symétrique. Ligne $L$ : $N$ entiers séparés par espaces, connexions de $L-1$, d’abord numéro du chemin vers 1, puis 2, etc. $A$ relié à $B$ implique l’inverse. Sans chemin, 0.

Sortie

Une ligne, un entier LCM des GCF de toutes les marches $1\to2$. Au plus 100 chiffres garantis.

Exemples

Entrée 1

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

Sortie 1

6

Auteur : Vlad Novakovski, 2002