בעקבות בוני הכבישים בין מדינות ארה״ב, הפרות ממספרות דרכי מרעה. $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.

פלט

שורה אחת שלם, 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