William loves strings and their properties, and he is especially fond of palindromes. He likes palindromes so much, that he started reading lots of research papers on them and finally stumbled upon a new kind of property that generalizes the palindrome concept: the *kalindrome*.

We say that a string is a \textit{kalindrome} if, for some positive integer $K$, it's possible to split the string in many substrings, each of them $K$ characters long, so that they can be ``read'' from left to right in the same way as right to left. More precisely: if we concatenate the substrings starting from the last one, we will recreate the original string.

We say that a string is a *kalindrome* if, for some positive integer $K$, it's possible to split the string in many substrings, each of them $K$ characters long, so that they can be ``read'' from left to right in the same way as right to left. More precisely: if we concatenate the substrings starting from the last one, we will recreate the original string.

For example: the word ``banaba'' is a kalindrome, because if we choose $K=2$ then we obtain the substrings: ba, na, ba, which can indeed be concatenated starting from the last one, to reconstruct the original word.

h2. Date de intrare

Fişierul de intrare $kalindrome.in$ ...

The input file $kalindrome.in$ contains the only integer $N$, $1 ≤ N ≤ 10^6$, the length of the string to be tested. The second line contains a string $S$, consisting of lowercase letters.

h2. Date de ieşire

În fişierul de ieşire $kalindrome.out$ ...

You will need to write in the output file $kalindrome.out$ a single line with an integer: the smallest positive integer $K$ that proves the kalindromeness of the string $S$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* For tests worth $40$ points, $K$ is either $1$ or $N$.
* For tests worth $40$ more points, $1 ≤ N \le 1000$.

h2. Exemplu
table(example). |_. kalindrome.in |_. kalindrome.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6
banaba
| 2
|
 
table(example). |_. kalindrome.in |_. kalindrome.out |
| 12
eszyciyciesz
| 3

|
h3. Explicaţie

...

In the first sample case, we can split the string in three $2$-characters long substrings: ba, na, ba.
 
In the second sample case, we can split the string in four $3$-characters long substrings: esz, yci, yci,
esz.

== include(page="template/taskfooter" task_id="kalindrome") ==