Minimum Generation Substring

Given a binary string S, determine the minimum non-negative integer generation G such that S appears as a substring in a recursively generated binary string. The binary string is generated using the following process:

• Base case: Generation 0 is 0.
• Recursive step: For each generation n > 0, the string is obtained by concatenating the string from generation n-1 with its bitwise complement. That is, if we denote the string at generation n-1 by S_n-1, then the string at generation n is \[ S_n = S_{n-1} \;||\; \overline{S_{n-1}}, \] where \( \overline{S_{n-1}} \) is formed by replacing every '0' with '1' and every '1' with '0'.

Your task is to find the smallest generation G (with G ≥ 0) for which the given string S is a substring of the recursively generated string for that generation. If no such generation exists within the safe limit (here, up to generation 10), output -1.

For example:

• For S = "01", the answer is 1.
• For S = "000", the answer is -1.
• For S = "0110", the answer is 2.

inputFormat

The input is read from the standard input (stdin) and has the following format:

T
S1
S2
...
ST

Here, T (an integer) represents the number of test cases, and each Si (a binary string) is a test case.

outputFormat

For each test case, output a single line containing the minimum generation G (an integer) on the standard output (stdout). If the given string does not appear as a substring in any generation within the safe limit, output -1.

## sample

3
01
000
0110

1
-1
2

</p>