Кубик Ріддіка

Як відомо, найпродаванішою іграшкою в історії є Кубик Рубіка. Загалом було продано понад $350$ мільйонів екземплярів.

Один казахський бізнесмен вирішив повторити цей успіх, створивши спрощену версію цієї головоломки. Кубик Ріддіка — це прямокутник розміром n \times m, що складається з клітинок 1 \times 1, кожна з яких має певний колір. За один хід дозволяється циклічно зсунути будь-який рядок або стовпець у будь-якому напрямку на одну клітинку. Наприклад, ось як зсувається $2$-й рядок вправо і $3$-й стовпець вгору:

Рішенням головоломки є така конфігурація, в якій у кожному рядку або стовпці всі клітинки одного кольору (виграшна конфігурація).

Для початку продажу головоломки необхідно оцінити її складність, чим Ви і повинні зайнятися. Для обчислення складності будемо використовувати спрощені правила: спочатку можна зсунути якісь стовпці (можливо жодні), а потім якісь рядки (можливо жодні).

Вам буде дано опис конфігурації Кубика Ріддіка. Якщо з заданої конфігурації можливо за спрощеними правилами отримати виграшну, то складність поточної конфігурації вважається рівною мінімальній кількості ходів, необхідних для досягнення виграшної. Якщо ж отримати виграшну конфігурацію за цими правилами неможливо, вважається, що складність дорівнює $100500$ (головоломка може бути все ще розв'язуваною за звичайними правилами, але вона занадто складна).