Description

回文串 是指正着读和反着读都一样的单词，例如 $\text{madam}$ 或 $\text{racecar}$。在本问题中，我们只考虑由小写字母组成的字符串。

我们新定义几种回文类型。如果一个字符串不是回文串，我们尝试通过移除字符串中最少数量的字符使其变为回文串。对于一个字符串 $w$，如果使其变为回文串所需移除的最小字符数为 $k$，则称字符串 $w$ 为 类型-$k$ 回文串。因此，如果 $w$ 是回文串，则 $w$ 是类型-$0$ 回文串。

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

Input Format

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

Output Format

你的程序需要向标准输出写入数据。输出恰好一行。该行应包含一个数字 $k$，取自 $\{0, 1, 2, 3, -1\}$。如果输入字符串是类型-$k$ 回文串且 $k = 0, 1, 2, 3$，则输出对应的 $k$；否则输出 $-1$。负数 $-1$ 表示输入字符串不是 $k = 0, 1, 2, 3$ 中的任何一种类型回文串。

aababaa

0

abccbbab

2

acmicpc

-1

Hint

翻译由 DeepSeek V3 完成