Description

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 $S$ of length $n$ can be measured by its palindromic length, $\text{PL}(S)$, which is the minimum number of palindromic substrings into which $S$ can be partitioned. More precisely, $\text{PL}(S)$ is the minimum number $t$ ($1 \leq t \leq n$) such that there exist palindromic substrings $S_1, S_2, \dots, S_t$ whose concatenation $S_1S_2 \cdots S_t$ becomes $S$. To make it easier to distinguish, we denote a partition of $S$ into $S_1, S_2, \dots, S_t$ as $S_1 \mid S_2 \mid \cdots \mid S_t$.

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

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

Input Format

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

Output Format

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

6
abaaca

2

5
acaba

3

5
abcde

5

5
radar

1