Shortest Good Interval

Given a string S consisting of lowercase English letters, your task is to find the length of the shortest substring (interval) that contains at least one occurrence of each of the letters a, b, and c. If no such substring exists, you should return -1.

More formally, if we denote by \(S[i\dots j]\) a substring of S (with 0-based indexing), you are to determine the minimum length \(L\) such that there exists \(i, j\) satisfying $$ \{a,b,c\} \subseteq \{S[k]: i \le k \le j\} $$ If no valid interval exists, then \(L = -1\).

inputFormat

The input starts with an integer T (1 ≤ T ≤ 10⁵) representing the number of test cases. Each of the following T lines contains a string S composed only of lowercase English letters.

outputFormat

For each test case, output a single integer in a new line representing the length of the shortest interval in S that contains at least one occurrence of each letter 'a', 'b', and 'c'. If no such interval exists, output -1.

3
abac
abcabc
aaa

3
3
-1