Palindromic Length

문제

A string is called a palindrome if it is read the same forward and backward. Palindromes are useful factors for measuring the complexity of strings like the asymmetry of the strings. The asymmetry of a string $SS$ of length $nn$ can be measured by its palindromic length, $PL(S)PL(S)$, which is the minimum number of palindrome substrings into which $SS$ can be partitioned. More precisely, $PL(S)PL(S)$ is the minimum number $tt$ (1 ≤ t ≤ n) such that there exist palindrome substrings $S_1,S_2,\dots ,S_{t}S\_1,\; S\_2,\; \backslash dots\; ,\; S\_t$ whose concatenation $S_1{S}_2\cdots S_{t}S\_1S\_2\; \backslash cdots\; S\_t$ becomes $SS$. To make it easier to distinguish, we denote a partition of $SS$ into $S_1,S_2,\dots ,S_{t}S\_1,\; S\_2,\; \backslash dots\; ,\; S\_t$ as $S_{1}S\_1$ | $S_{2}S\_2$ | $\cdots \backslash cdots$ | $S_{t}S\_t$.

For example, a string $S=S\; =$abaaca can be partitioned into two palindrome substrings as aba | aca, that is the minimum, so $PL(PL($abaaca$)=2)\; =\; 2$. A string acaba cannot be partitioned into two palindrome substrings, but it can be partitioned into three palindrome substrings, $S=S\; =$aca | b | a or $S=S\; =$a | c | aba, so $PL(PL($acaba$)=3)\; =\; 3$. For $S=S\; =$radar, $PL(S)=1PL(S)\; =\; 1$ because $SS$ is a palindrome. $PL(S)=5PL(S)\; =\; 5$ for $S=S\; =$abcde.

Given a non-empty string $SS$ of English lowercase letters, write a program to output $PL(S)PL(S)$.

입력

Your program is to read from standard input. The input starts with a line containing a positive integer $nn$ (1 ≤ n ≤ 100\,000), where $nn$ is the number of letters of a string. The next line contains a string of $nn$ English lowercase letters. Note that the string contains no space between the letters.

출력

Your program is to write to standard output. Print exactly one line. The line should contain a positive integer which is the palindromic length $PL(S)PL(S)$ of the input string $SS$.