Разгадав словарь древнеберляндского языка, ученые смогли прочитать записи летописцев того времени. В частности, они узнали, как происходил выбор вождя древнеберляндского племени.

Как только на место вождя набиралось достаточное количество претендентов, среди них проводилось следующее испытание: шаман племени брал плиту, разделенную вертикальными и горизонтальными полосам на одинаковые клетки (плита состояла из N строк и M столбцов), и красил каждую клетку в черный или белый цвет. Затем каждому испытуемому выдавалась плита такого же размера, но покрашенная полностью в белый цвет. За один день он мог перекрасить любое связное по стороне множество клеток этой плиты в некоторый цвет. Множество называется связным, если для любых двух клеток этого множества существует путь, все клетки которого принадлежат этому множеству, и любые две соседние клетки на этом пути имеют общую сторону. Цель каждого из претендентов — получить в точности такую же раскраску как у шамана. Тот, кто получал такую раскраску раньше всех, становился новым вождем племени.

Ученые обнаружили плиту, раскрашенную шаманом древнеберляндского племени. Помогите им определить, за какое минимальное количество дней мог определиться новый вождь, если ему нужно было получить заданную раскраску.