미국 주간 고속도로 건설자를 본떠 소는 목초지 도로 번호를 도입했습니다. $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)를 구합니다. 예 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.

출력

한 줄 정수, 모든 $1\to2$ 산책 GCF의 LCM, 100자리 이하 보장.

예제

입력 1

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

출력 1

6

문제 작성: Vlad Novakovski, 2002