Вам дано клетчатое поле из n строк и n столбцов. Каждая клетка либо пуста (обозначается символом «.»), либо занята (обозначается символом «X»).

Две пустые клетки соединены напрямую, если у них есть общая сторона. Две клетки (r₁, c₁) (то есть клетка, расположенная в ряду r₁ и столбце c₁) и (r₂, c₂) соединены путём, если существует последовательность пустых клеток, начинающаяся с (r₁, c₁) и заканчивающаяся на (r₂, c₂), такая что любые две соседние клетки последовательности соединены напрямую. Компонентой связности называется множество пустых клеток, такое что любые две клетки множества соединены путём, и при этом никакая клетка множества не соединена путём ни с какой пустой клеткой не из этого множества.

Ваш друг Лимак — большой медведь гризли, способный разрушать препятствия в некоторой области. Точнее, вы можете попросить Лимака разрушить все препятствия в некотором квадрате k × k, то есть превратить все занятые клетки в свободные. Однако попросить помощи у Лимака можно только один раз.

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

Вы любите большие компоненты связности. Какую самую большую компоненту связности можно получить, попросив Лимака о помощи не более одного раза?