Time Limit: 1000 MS    Memory Limit: 65536 K 


Description

Given a string A with length N. A0 A1 A2 A3 ...... AN-1 S(0) = A0 A1 A2 A3 ...... AN-2 AN-1 S(1) = A1 A2 A3 ...... AN-2 AN-1 A0 S(2) = A2 A3 ...... AN-2 AN-1 A0 A1 ...... S(N-1) = AN-1 A0 A1 A2 A3 ...... AN-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 <= N <= 1000

Output

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

Sample Input

3 aaa abab aba

Sample Output

3 2 1

Source

onmylove@scuacm Sichuan University Programming Contest 2012 Preliminary