A string is called a \(Good\) string if it has the following properties:

• The length of the string is >=2
• The first and the last character of the string are identical.

You are given a string S of length N (N >=2) . You have to make it \(Good\) string using the following operations.

• \( Operation 1\): Remove a letter from the beginning of the string.
• \(Operation2\): Remove a letter from the end of the string.
  

You can apply the \(Operation1\) or \(Operation2\) or both on the string S. Now your task is to find out the minimum number of operations to make the string S a \(Good\) string.

Input:
The first line of the input will contain T , the number of testcases.
Next line will contain a string of a certain length. The string will consist of only lower case letters from 'a' to 'z'.

Output:
Print the minimum no of operations required. If impossible print "-1", without quotes .

Constraints:

• \(1 \le T \le 100\)
• \(2 \le N \le 10^4\)