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