回文串是指正读反读都相同的字符串，例如 $madam$ 或 $racecar$。在本题中，我们仅考虑由小写字母组成的字符串。

我们重新定义回文串的类型。如果一个字符串不是回文串，我们尝试通过删除字符串中最少数量的字符使其成为回文串。对于字符串 $w$，如果将其变为回文串所需删除的最少字符数为 $k$，则称该字符串 $w$ 为 $k$ 型回文串。因此，如果 $w$ 本身就是回文串，则 $w$ 为 0 型回文串。

给定一个字符串 $w$，编写一个程序来判断 $w$ 是否为 $k$ 型回文串，其中 $k = 0, 1, 2, 3$。

输入格式

程序从标准输入读取数据。输入为一行，包含一个长度为 $n$ ($5 \le n \le 10^5$) 的小写字母字符串 $w$。

输出格式

程序向标准输出写入数据。输出仅一行。如果输入字符串是 $k$ 型回文串（$k \in \{0, 1, 2, 3\}$），则输出对应的数字 $k$；否则输出 $-1$。负数 $-1$ 表示输入字符串不是 $k \in \{0, 1, 2, 3\}$ 型的回文串。

样例

输入 1

aababaa

输出 1

0

输入 2

abccbbab

输出 2

2

输入 3

acmicpc

输出 3

-1