Theo các nhà xây cao tốc liên bang Mỹ, bò đặt số đường giữa đồng cỏ. $N$ đồng ($2\le N\le25$) số $1\ldots N$, mỗi đường số khác nhau $1\ldots2000$, như I-9,I-16.

Ví dụ đồng 1,2,3,4 nối bằng I-3,I-6,I-9,I-16:

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

Bessie thích đi từ 1 tới 2 trên hệ mới, không ghé một đồng hai lần: 1-4-2, 1-3-2 trong ví dụ.

Qua nhiều năm phát triển tài toán kinh ngạc, mỗi lượt tìm ước chung lớn nhất (GCF) số đường đi qua. 1-4-2 qua I-16,I-6, GCF 2: 16 và 6 chia hết cho 2, không số nguyên lớn hơn nào là ước của cả hai.

Ngày qua ngày đi mọi đường $1\to2$, nhớ GCF. Sau khi đi tất cả đường có thể, mỗi đường một lần, tính bội chung nhỏ nhất (LCM). Ví dụ 2,3: $\gcd(6,16)=2$, $\gcd(3,9)=3$, LCM 6.

Mạng lớn có thể mệt, nhưng muốn LCM mọi bản đồ. Hãy tính.

Dữ liệu vào

• Dòng 1: $N$.
• Dòng $2..N+1$: $N$ dòng ma trận đối xứng. Dòng $L$: $N$ số nguyên cách bằng khoảng trắng, nối $L-1$, đầu số đường tới 1, hai tới 2, v.v. $A$ nối $B$ thì ngược lại. Không đường, 0.

Dữ liệu ra

Một dòng số nguyên LCM mọi GCF lượt đi $1\to2$, bảo đảm tối đa 100 chữ số.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

6

Tác giả: Vlad Novakovski, 2002