Problem A
I Repeat Myself I Repeat Myself I Repeat

The Perl programming language has a lot of convenient little operators. For example, it has an infix operator, x, for creating repeated copies of a string. When used in an expression like $p$ x $n$, the operator x produces a string containing $n$ repeated copies of the string $p$.

For this problem, you are going to look for cases where a long input string consists of a repeated pattern. We say string $s_1$ is a prefix of string $s$ if there exists some (possibly empty) string $s_2$ such that $s$ is the concatenation of $s_1$ and $s_2$. We say pattern $p$ explains string $s$ if $s$ is a prefix of $p$ x $n$ for some sufficiently large $n$.

Input

Input starts with an integer, $1\le n\le 200$. This is followed by $n$ test cases, one per line. Each input line consists of a non-empty sequence of up to 70 printable ASCII characters.

Output

For every test case, print a single output line giving the length of the shortest pattern that explains the given input string.

3
I Repeat Myself I Repeat Myself I Repeat
aaaaaaaaaaaaaaaaaaaaa
abbcabbcabbabbcabb

16
1
11