A boy named Misha, after reading "The Master and Margarita," became afraid of trams, tracks, and everything related to them. To overcome his fear, Misha decided to build a tram system in a well-known computer game about cubes and study the properties of the constructed system.
Misha chose an even number $$$n$$$ and built $$$n^2$$$ stations, forming an $$$n \times n$$$ grid, then connected them using $$$\frac{n}{2}$$$ cyclic non-intersecting railways, forming nested squares.
At each of the $$$n^2$$$ stations, Misha placed one tram, each of which had one of $$$26$$$ types, denoted by lowercase letters of the Latin alphabet. Since the stations form an $$$n \times n$$$ grid, it is easy to write the types of all the trams in a table.
It should be clarified that Misha was not so much afraid of the trams themselves, but of the dark forces. Therefore, he carefully monitored the amount of mysticism, which can be calculated as follows:
Consider the table with the tram types at each station, then all tram types are written in a single string $$$s$$$ (first the first row of the table is written, then the second, and so on). The mysticism is defined as the length of the longest prefix of $$$s$$$ that matches the reversed suffix of $$$s$$$ of the same length.
Misha understands that if the tram system is launched, the trams will change their positions; specifically, on each track, the trams can shift in a cycle, and the shift may occur by different amounts on different tracks. Misha is interested in the maximum possible value of mysticism across all possible tram positions.
Unfortunately, Misha is not as smart as you are, so he asks you to help him calculate the value he is interested in.
The first line contains an even natural number $$$n$$$ ($$$2 \le n \le 1000$$$).
The following $$$n$$$ lines describe the configuration of the tram system—each line contains $$$n$$$ lowercase Latin letters written consecutively—the types of trams located in that row.
In a single line, output a single number—the maximum possible value of mysticism.
4aefcbddaaddbcefa
4
4aaaaaaaaaaaaaaaa
16
Consider the first example. In it, the outer tram line can be cyclically shifted by $$$3$$$ trams clockwise. Then the following situation arises:
If after that all tram types are written in a single line, the resulting string will be cabaedbefddfabac. It is clear that in this string, the prefix of length $$$4$$$ matches the reversed suffix of length $$$4$$$, so the mysticism after the specified manipulations equals $$$4$$$. It can be shown that a greater value of mysticism is impossible.
In the second example, trams can be cyclically shifted arbitrarily; in any case, the resulting string will have the form aaa ... aaa, which is itself a suffix and prefix, and is also a palindrome, so the mysticism equals $$$16$$$.
