Современное искусство

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. Поскольку мы не видим других цветов, мы делаем вывод, что они также могли быть использованы первыми (а потом перекрашены).