Paper Folding

Hektor is very bored during class, so he invented a game to keep himself busy. He cut out a strip of paper and wrote a string of 0s and 1s on it (for example 10000101011). Now he folds the strip between two adjacent symbols so that the folded part lines up with the part it is folded onto. The rule is that the symbols in the overlapping region must be equal. Hektor always folds the left side over to the right: the segment to the left of the crease is flipped and laid on top of the segment to its right.

For example, folding 10000101011 between the third and fourth symbols yields 00101011, and folding it between the second-to-last and last symbols yields 1010100001. After a fold, the length of the strip becomes the length of the longer of the two segments.

Hektor wants to fold the strip (possibly many times) so that it ends up as short as possible. For instance, 10011001 can be reduced to 01 (length $2$): first fold between the fourth and fifth symbols to get 1001, then fold between the second and third symbols.

Determine the shortest length the strip can reach through folding.

The first line contains an integer $t$, the number of test cases ($1 \le t \le 20$). Then $t$ test cases follow.

Each test case consists of a single line containing the description of Hektor's strip: a string of 0s and 1s with no separators. The string has length between $1$ and $100$ inclusive.

For each test case, print on its own line a single integer: the length of the shortest strip obtainable by folding (possibly multiple times).