Shortest Balanced Substring

You are given a string consisting only of the characters 'a', 'b', and 'c'. A substring of this string is called balanced if it contains an equal number of 'a', 'b', and 'c'. In other words, a substring (S[i\ldots j]) is balanced if and only if (\text{count}_a = \text{count}_b = \text{count}_c) in that substring. Your task is to determine the length of the shortest balanced substring for each given test case. If no such substring exists, output -1.

Note: The balanced substring must have a length that is at least 3 since at least one instance of each character is required.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) representing the number of test cases. Each of the following (T) lines contains a single string consisting of only the characters 'a', 'b', and 'c'.

outputFormat

For each test case, print on a new line the length of the shortest balanced substring. If no balanced substring exists, print (-1). The output is printed to the standard output (stdout).## sample

3
abccba
abcabcabc
aaabbbccc

3
3
9