Недавно Миша нашел квадратную матрицу \(n \times n\), где в клетке на пересечении строки \(i\) и столбца \(j\) записано число \(a_{i, j}\). После этого Миша решил немного изменить матрицу, чтобы количество различных чисел в ней стало ровно \(k\). Для этого он может любое число раз (возможно, ноль) применить следующую операцию:
- выбрать любую квадратную подматрицу (выбираются \((x_1,y_1)\), \((x_2,y_2)\), такие что \(x_1 \leq x_2\), \(y_1 \leq y_2\), \(x_2 - x_1 = y_2 - y_1\), тогда подматрицей называется множество клеток с координатами \((x, y)\), такими что \(x_1 \leq x \leq x_2\), \(y_1 \leq y \leq y_2\)),
- выбрать число \(k\), где \(1 \leq k \leq n^2\),
- заменить все числа в выбранной подматрице на \(k\).
Пожалуйста, найдите минимальное количество операций, которые нужны, чтобы Миша достиг своей цели.
Выходные данные
Выведите одно число — искомое минимальное число операций.
Примечание
В первом примере ответ \(1\), так как можно заменить число в правом нижнем углу таблички на \(1\). Получится такая матрица:
Во втором примере ответ \(2\). Можно сначала заменить все значения матрицы на \(1\), а потом заменить число в любой клетке на \(2\). Получится такая матрица:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
1 1 1
1 1 2
3 4 5
|
1
|
|
2
|
3 2
2 1 3
2 1 1
3 1 2
|
2
|
|
3
|
3 3
1 1 1
1 1 2
2 2 2
|
1
|
|
4
|
3 2
1 1 1
1 2 1
2 2 2
|
0
|