Marichka 在上网时看到了一个坏词！她立刻哭了起来，并请求 Zenyk 销毁它。

Zenyk 知道 Marichka 看到的词 $S$ 由小写英文字母组成。Zenyk 可以在一分钟内删除该词的任意子串 $S_l S_{l+1} S_{l+2} \dots S_r$。但他知道 Marichka 非常喜欢回文串，所以如果这个子串是回文串，Marichka 会感到不满。Zenyk 决定不删除这样的子串。现在 Zenyk 想知道销毁这个坏词所需的最短时间，如果无法销毁，则输出 $-1$。

回文串是指正读和反读都相同的字符串。例如，“bob”、“abba”、“aaaa” 是回文串，而“cat”、“dog”、“penguin” 则不是。

输入格式

第一行包含一个整数 $N$ —— 词 $S$ 的长度 ($1 \le N \le 10^5$)。第二行包含由小写英文字母组成的词 $S$。

输出格式

输出销毁坏词所需的最短分钟数，如果无法销毁，则输出 $-1$。

样例

输入 1

7
abcdcba

输出 1

2

输入 2

3
xxx

输出 2

-1

说明

在第一个样例中，Zenyk 可以在第一分钟删除子串 “bcd”。剩余的词变为 “acba”，可以在第二分钟被删除。