如果一个字符串从前往后读和从后往前读是一样的，则称其为回文串。回文串是衡量字符串复杂度（如字符串不对称性）的有用因子。长度为 $n$ 的字符串 $S$ 的不对称性可以通过其回文长度 $PL(S)$ 来衡量，即 $S$ 可以被划分成的最少回文子串数量。更准确地说，$PL(S)$ 是满足存在回文子串 $S_1, S_2, \dots, S_t$ 且它们的拼接 $S_1 S_2 \dots S_t$ 等于 $S$ 的最小整数 $t$ ($1 \le t \le n$)。为了便于区分，我们将 $S$ 划分为 $S_1, S_2, \dots, S_t$ 的过程记作 $S_1 | S_2 | \dots | S_t$。

例如，字符串 $S = abaaca$ 可以划分为两个回文子串 $aba | aca$，这是最小值，因此 $PL(abaaca) = 2$。字符串 $acaba$ 不能划分为两个回文子串，但可以划分为三个回文子串，即 $S = aca | b | a$ 或 $S = a | c | aba$，因此 $PL(acaba) = 3$。对于 $S = radar$，$PL(S) = 1$，因为 $S$ 本身就是一个回文串。对于 $S = abcde$，$PL(S) = 5$。

给定一个由小写英文字母组成的非空字符串 $S$，编写一个程序输出 $PL(S)$。

输入格式

程序从标准输入读取数据。输入的第一行包含一个正整数 $n$ ($1 \le n \le 100,000$)，表示字符串的长度。下一行包含一个由 $n$ 个小写英文字母组成的字符串。注意，字符串中字母之间没有空格。

输出格式

程序将结果写入标准输出。仅打印一行，包含一个正整数，即输入字符串 $S$ 的回文长度 $PL(S)$。

样例

输入 1

6
abaaca

输出 1

2

输入 2

5
acaba

输出 2

3

输入 3

5
abcde

输出 3

5

输入 4

5
radar

输出 4

1