Вдохновившись строителями межштатных шоссе США, коровы ввели номера межпастбищных дорог. $N$ пастбищ ($2\le N\le25$) имеют $1\ldots N$, каждая дорога свой уникальный номер $1\ldots2000$, например I-9 и I-16.

Пример: пастбища 1,2,3,4 соединены I-3,I-6,I-9,I-16:

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

Bessie любит ходить по новой системе из 1 в 2, не посещая пастбище дважды: пути примера 1-4-2 и 1-3-2.

За годы она развила удивительную математику и ищет на прогулке наибольший общий делитель (GCF) номеров дорог. 1-4-2 проходит I-16 и I-6, GCF 2: 2 делит 16 и 6, большее целое не делит оба.

День за днём проходит все пути $1\to2$ и запоминает GCF. После того как пройдёт все возможные пути по одному разу, считает наименьшее общее кратное (LCM). В примере GCF 2,3: $\gcd(6,16)=2$, $\gcd(3,9)=3$, LCM 6.

На большой сети устаёт, но хочет LCM каждой карты. Вычислите его.

Входные данные

• Строка 1: $N$.
• Строки $2..N+1$: $N$ строк симметричной матрицы. Строка $L$ содержит $N$ целых через пробел: связь $L-1$ с другими, первый номер дороги к 1, второй к 2 и т. д. Связь $A$ с $B$ означает обратную. Нет дороги — 0.

Выходные данные

Одна строка с целым LCM всех GCF прогулок $1\to2$. Гарантировано не более 100 цифр.

Примеры

Входные данные 1

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

Выходные данные 1

6

Автор задачи: Vlad Novakovski, 2002