Palindromic Length

A string is called a palindrome if it reads the same forward and backward. Palindromes are useful for measuring the complexity of strings, such as their asymmetry.

The asymmetry of a string $S$ of length $n$ can be measured by its palindromic length, $PL(S)$. This is the minimum number of palindromic substrings into which $S$ can be partitioned. More precisely, $PL(S)$ is the minimum $t$ ($1 \le t \le n$) such that there exist palindromic substrings $S_1, S_2, \dots, S_t$ whose concatenation $S_1 S_2 \cdots S_t$ equals $S$. A partition of $S$ into $S_1, S_2, \dots, S_t$ is written as $S_1$ | $S_2$ | $\cdots$ | $S_t$.

For example, abaaca can be partitioned into two palindromic substrings as aba | aca, and two is the minimum, so $PL(S) = 2$ for abaaca. The string acaba cannot be split into two palindromes, but it can be split into three: aca | b | a or a | c | aba, so $PL(S) = 3$ for acaba. For radar, $S$ is itself a palindrome, so $PL(S) = 1$. For abcde, $PL(S) = 5$.

The first line contains a positive integer $n$ ($1 \le n \le 100\,000$), the number of letters in the string. The next line contains a string of $n$ English lowercase letters. The letters are not separated by spaces.

Print exactly one line containing the palindromic length $PL(S)$ of the input string $S$. The value is a positive integer.