Сучасне мистецтво

Picowso - новий геній!

Picowso малює унікальним способом. Вона починає з порожнього полотна розміром n * n клітинок, яке представлено ґраткою з n * n нулів, де нуль означає порожню клітинку полотна. Далі вона малює n^2 прямокутників на полотні, використовуючи n^2 кольорів, пронумерованих послідовно від 1 до n^2. Наприклад, вона може почати з малювання прямокутника кольором 2, і тоді полотно виглядатиме так:

2 2 2 0 
2 2 2 0 
2 2 2 0 
0 0 0 0

Потім вона може додати прямокутник кольором 7:

2 2 2 0 
2 7 7 7 
2 7 7 7 
0 0 0 0

А потім намалювати маленький прямокутник кольором 3:

2 2 3 0 
2 7 3 7 
2 7 7 7 
0 0 0 0

Кожен прямокутник має сторони, паралельні сторонам полотна, і може бути розміром від усього полотна до однієї клітинки. Кожен колір з 1 до n^2 використовується рівно один раз, хоча пізніші кольори можуть повністю перекривати попередні.

За даним фінальним станом полотна визначте, скільки з n^2 кольорів могли бути першими використаними при малюванні.

Вхідні дані

Перший рядок містить розмір полотна n (1 ≤ n ≤ 1000). Наступні n рядків описують фінальну картину на полотні, кожен рядок містить n цілих чисел у діапазоні від 0 до n^2. Гарантується, що картина була створена описаним вище способом, шляхом малювання прямокутників різних кольорів.

Вихідні дані

Виведіть кількість кольорів, які могли бути використані першими.

Приклади

Примітка

У цьому прикладі колір 2 міг бути використаний першим. Колір 3 був використаний після кольору 7, а колір 7 був використаний після кольору 2. Оскільки ми не бачимо інших кольорів, ми робимо висновок, що вони також могли бути використані першими (а потім перемальовані).