A palindrome string is a word which reads the same backward as forward, such as madam or racecar. In this problem we only consider strings with lowercase alphabets.</p>

We newly define the types of palindromes. If a string is not a palindrome, we try to make it a palindrome by removing the minimum number of characters in the string. For a string $w$, if $k$ is the minimum number of characters removed to make the string a palindrome, we call the string $w$ type-$k$ palindrome. Thus, if $w$ is a palindrome, then $w$ is a type-$0$ palindrome.

Given a string $w$, write a program to determine if $w$ is a type-$k$ palindrome where $k = 0, 1, 2, 3$.

입력 형식

Your program is to read from standard input. The input is a single line containing a string $w$ with length $n$ ($5 ≤ n ≤ 10^5$) of lowercase alphabets.

출력 형식

Your program is to write to standard output. Print exactly one line. The line should contain a number $k$ among ${0, 1, 2, 3, -1}$ if the input string is a type-$k$ palindrome where $k = 0, 1, 2, 3$ and otherwise $-1$. The negative number $-1$ means the input string is not a type-$k$ palindrome where $k = 0, 1, 2, 3$.

예제 입력 1

aababaa

예제 출력 1

0

예제 입력 2

abccbbab

예제 출력 2

2

예제 입력 3

acmicpc

예제 출력 3

-1