You are a given a string $s$ of length $n$. Find the length of the shortest palindrome that is a substring of $s$ and is at least 2 characters long, or report that no such substring exists. $s$ consists of lowercase Latin alphabet.

Input

A single line contains a string $s$.

Output

Print the length of the shortest palindromic substring or -1 if no such string exists.

Constraints

• $2 \leq n \leq 10^5$

Example 1

Input:

abba

Output:

2

Example 2

Input:

zsyad

Output:

-1

Example 4

Input:

aybabtu

Output:

3