Migrated from Lutece 591 Windy's S(II)

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Given a string $A$ with length $N$.

$A_0, A_1, A_2, A_3 \cdots A_{N-1}$

$S(0) = A_0, A_1, A_2, A_3 \cdots A_{N-2}, A_{N-1}$

$S(1) = A_1, A_2, A_3 \cdots A_{N-2}, A_{N-1}, A_0$

$S(2) = A_2, A_3 \cdots A_{N-2}, A_{N-1}, A_0, A_1$

......

$S(N-1) = A_{N-1}, A_0, A_1, A_2, A_3 \cdots A_{N-2}$

Windy want to know how many $i$ in $[0, N - 1]$ that make $S(i)$ euqal to $S(0)$.

Can you find it for Windy?

Input

The first line of input is the number of test case.

For each test case, there is only one line contains a string $A$.

String $A$ only contains lowercase letter (a--z).

$1 \leq N \leq 1000$

Output

For each test case output the answer on a single line.

Samples

3
aaa
abab
aba

3
2
1

Resources

Sichuan University Programming Contest