Пусть задана матрица b размера x × y, определим операцию разворота матрицы b. Разворотом матрицы b называется матрица c размера 2x × y, обладающая свойствами:
- верхняя половина матрицы c (строки с номерами от 1 до x) в точности равна b;
- нижняя половина матрицы c (строки с номерами от x + 1 до 2x) симметрична верхней относительно линии раздела двух половин (линия, проходящая посередине между строками x и x + 1).
У Сережи есть матрица a размера n × m. Он хочет найти такую матрицу b, что из нее можно получить матрицу a, выполнив несколько (возможно, ноль) разворотов. Какое минимальное количество строк может содержать такая матрица?
Выходные данные
В единственную строку выведите ответ на задачу — минимальное количество строк матрицы b.
Примечание
Во первом тестовом примере ответом является матрица b размера 2 × 3:
001
110
Если применить к этой матрице операцию разворота, получится заданная во входных данных матрица a:
001
110
110
001
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
0 0 1
1 1 0
1 1 0
0 0 1
|
2
|
|
2
|
3 3
0 0 0
0 0 0
0 0 0
|
3
|
|
3
|
8 1
0
1
1
0
0
1
1
0
|
2
|