اقتداءً ببناة الطرق بين الولايات الأمريكية، أدخلت الأبقار ترقيم طرق المراعي. $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، والقاسم 2: يقسم 16 و6 ولا صحيح أكبر يقسمهما.

يومًا بعد يوم تعبر كل مسارات $1\to2$ وتتذكر GCF. بعد اجتياز جميع المسارات الممكنة مرة واحدة لكل مسار تحسب المضاعف المشترك الأصغر (LCM). مثال 2,3: $\gcd(6,16)=2$، $\gcd(3,9)=3$، المضاعف 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