Однажды Магнус решил разыграть одну классическую шахматную партию. Но открыв чулан, Магнус пришел в ужас! Его любимая доска была разломлена на 4 части, каждая размера n на n, причем n обязательно нечетно. Хуже того, некоторые клетки имели неправильный цвет. j-я клетка i-й строки k-й части доски имеет цвет ak, i, j; 1 соответствует черному цвету, а 0 — белому.
Магнусу стало интересно, какое минимальное количество клеток нужно перекрасить, чтобы из частей доски можно было составить правильную доску. В правильной доске любая пара соседних по стороне клеток должна иметь различный цвет, и размер правильной доски должен быть 2n на 2n. Части доски разрешено переставлять, но нельзя поворачивать или переворачивать.
Выходные данные
Выведите одно число — минимальное количество клеток, которые необходимо перекрасить, чтобы из них можно было составить правильную доску.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
0
0
1
0
|
1
|
|
2
|
3
101
010
101
101
000
101
010
101
011
010
101
010
|
2
|