Мальчик Миша после прочтения Мастера и Маргариты стал бояться трамваев, рельсов и всего с этим связанного. Чтобы преодолеть свой страх, Миша решил построить трамвайную систему в известной компьютерной игре про кубики и изучить свойства построенной системы.

Миша выбрал четное число $$$n$$$ и построил $$$n^2$$$ станций, формирующих сетку $$$n \times n$$$, затем соединил их с помощью $$$\frac n2$$$ зацикленных не пересекающихся рельсовых путей, образующих вложенные квадраты.

На каждой из $$$n^2$$$ станций Миша разместил по одному трамваю, каждый из которых имел один из $$$26$$$ типов, обозначаемых строчными буквами латинского алфавита. Ввиду того, что станции образуют сетку $$$n \times n$$$, легко записать в виде таблицы типы всех расставленных трамваев.

Стоит уточнить, что Миша боялся не столько самих трамваев, сколько темных сил. Поэтому он внимательно следил за величиной мистики, которую можно вычислить следующим образом:

Рассматривается таблица с записанными типами трамваев у каждой из станций, затем все типы трамваев выписываются в одну строку $$$s$$$ (сначала выписывается первая строка таблицы, затем вторая и так далее). Уже при вычисленной строке $$$s$$$ мистика определяется как длина наибольшего префикса $$$s$$$, который совпадает с развернутым суффиксом $$$s$$$ такой же длины.

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

К сожалению, Миша не такой умный, как вы, а поэтому просит вас ему помочь и вычислить интересующее его значение.