C. Matritsa

Time limit : 1000 ms
Memory limit : 64 mb

Sizga $n \cdot n$ o’lchamli matritsa berilgan. Sizning vazifangiz uning asosiy diaganalida yotuvchi elementlarning $EKUB$ ini topuvchi dastur tuzish.


Kiruvchi ma’lumotlar: Birinchi qatorda bitta butun son $n$ matritsa o’lchami berilgan$(1 \le n \le 15)$. Keyinga $n$ ta qatorning har birida $n$ ta sondan iborat matritsa elementlari berilgan. Matritsa elementlarining qiymatlari butun va $[1..10^9]$ intervalda yotadi.


Chiquvchi ma’lumotlar: Bitta sonni – masalaning javobini chiqaring.

Input
2
4 5
5 6
Output
2
Input
3
15 5 1
1 25 36
4 45 55
Output
5
Input
1
10
Output
10