Вишиванка Антона

У Антона є велика колекція різних вишиванок, кожна з яких має різні магічні сили.

Сила вишиванки визначається її візерунком і визначається найбільшим руном, який можна ідентифікувати в ній. Візерунок — це квадратна матриця розміру $n$, що складається з синіх і жовтих клітинок. Руну розміру $k$ можна представити як $4$ ідентичні шахові дошки розміру $2k-1$ (з синьою клітинкою у верхньому лівому куті), розташовані у формі "+"-хреста (утвореного однією вертикальною і однією горизонтальною лініями) з отвором посередині. Ми вважаємо, що руна розміру $k$ є в візерунку, якщо і тільки якщо ми можемо розмістити нашу руну на полі так, що сині клітинки в руні відповідають синім клітинкам у візерунку. Зверніть увагу, що не обов'язково, щоб жовті клітинки в руні відповідали; вони можуть співпадати як з синіми, так і з жовтими клітинками в візерунку.

Ось приклад руни розміру $2$ (чотири візерунки цієї руни позначені зеленими квадратами навколо них):

Зверніть увагу, що будь-яка група жовтих клітинок у цьому візерунку також може бути синьою, і руна все одно існуватиме:

Також, будь ласка, зверніть увагу, що це не руна розміру $1$, оскільки візерунки повинні бути розташовані у формі «+»-хреста:

Антону терміново потрібно знати силу вишиванки перед тим, як вдягнути її, але, на жаль, в той час він був дуже зайнятий, тому він попросив Чмякса (ще не злого) написати програму, яка визначатиме силу вишиванки на основі візерунка. Однак Чмякс обманув його і, вкравши щось важливе, втік. Тому зараз Антон просить вас це зробити.

Вхідні дані

Перший рядок містить одне ціле число $n$ $(1\le n\le 4,000)$ — розмір заданого візерунка.

Кожен з наступних $n$ рядків містить $n$ символів, кожен з яких є або «.», або «#», де «.» представляє жовту клітинку, а «#» — синю клітинку.

Вихідні дані

У єдиному рядку вам потрібно вивести силу заданого візерунка.

Зверніть увагу, що, якщо і тільки якщо на візерунку немає рун, відповідь буде $0$.

Приклади

Примітка

Максимальна руна на візерунку з першого прикладу має розмір одиниці:

Руна на візерунку з другого прикладу показана на зображеннях в умові. Можна показати, що на ній немає руни розміру $3$.

Ось вишиванка з третього прикладу:

Ось єдина руна розміру $1$, яку можна знайти на ній:

Можна показати, що тут немає рун розміру $2$ або більше.

У четвертому прикладі можна показати, що тут немає рун взагалі. Знову ж таки, будь ласка, зверніть увагу, що відповідь може бути $0$.

Оцінювання

1. ($24$ бали): гарантується, що відповідь не перевищує $2$;

2. ($26$ балів): $n\le 70$;

3. ($37$ балів): $n\le 300$;

4. ($31$ бал): $n\le 1,000$;

5. ($52$ бали): $n\le 2,500$;

6. ($80$ балів): немає додаткових обмежень.