Palindrome Type

문제

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.

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\le n\le {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

예제 입력 2 복사

abccbbab

예제 입력 3 복사

acmicpc

예제 출력 1 복사

0

예제 출력 2 복사

2

예제 출력 3 복사

-1