Problem Statement

Takahashi is writing a program to analyze the structure of strings.

A border of a string S is a string T that satisfies all of the following conditions:

• T is not the empty string.
• The length of T is strictly less than the length of S (i.e., |T| < |S|).
• T is both a prefix and a suffix of S. That is, the first |T| characters of S match T, and the last |T| characters of S also match T.

For example, the only border of the string abcab is ab. This is because ab matches both the first 2 characters and the last 2 characters of abcab, is non-empty, and has length strictly less than that of abcab. On the other hand, a matches the first 1 character but does not match the last 1 character (b), so it is not a border.

As another example, the string abababab has 3 borders: ab, abab, and ababab, with lengths 2, 4, 6 respectively.

Note that for a positive integer \ell less than |S|, the string consisting of the first \ell characters of S is uniquely determined, and whether it matches the last \ell characters of S is also uniquely determined. Therefore, there is at most one border of each length, and the set of borders is in one-to-one correspondence with the set of their lengths.

Takahashi receives Q strings and wants to compute the following value for each of them.

Let k be the number of borders of string S. When k \geq 1, let d_1 < d_2 < \dots < d_k be the sequence of all border lengths sorted in ascending order (since all border lengths are distinct, this sequence is strictly increasing). Compute the following value:

• If k = 0 (no border exists): output 0.
• If k = 1 (exactly one border): output the length of that border, d_1.
• If k \geq 2 (two or more borders): the differences between adjacent elements d_2 - d_1,\, d_3 - d_2,\, \dots,\, d_k - d_{k-1} are all positive integers. Output the greatest common divisor of these k-1 positive integers.

In the example above, the border lengths of abababab are d_1 = 2,\, d_2 = 4,\, d_3 = 6, so the differences between adjacent elements are d_2 - d_1 = 2,\, d_3 - d_2 = 2, and their greatest common divisor is 2.

Constraints

• 1 \leq Q \leq 10^5
• The length |S_i| of each string S_i satisfies 1 \leq |S_i| \leq 10^6.
• S_i consists of lowercase English letters.
• The total length of all strings satisfies \displaystyle \sum_{i=1}^{Q} |S_i| \leq 10^6.

Sample Input 1

5
abcab
abababab
aaaa
abcde
aba

Sample Output 1

2
2
1
0
1

Sample Input 2

6
a
aa
ab
abcabc
zzz
xyxxyx

Sample Output 2

0
1
0
3
1
2

Sample Input 3

8
abcababcab
aaaaabaaaaab
abababa
abcabcabcabc
abcdabcabcd
zzxyzzxyzz
mississippi
aabaaabaaab

Sample Output 3

3
6
2
3
4
1
0
4

Sample Input 4

10
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
abababababababababababababababababababababababababababababababab
abcabcabcabcabcabcabcabcabcabcabcabcabcabc
abcdabcdabcdabcdabcdabcdabcdabcdabcdabcd
thequickbrownfoxjumpsoverthelazydogthequickbrownfox
zzzzzyzzzzzyzzzzzyzzzzzyzzzzzy
aabbaabbaabbaabbaabbaabbaabbaabb
abcdeffedcbaabcdeffedcbaabcdeffedcba
mnopqrmnopqrmnopqrmnopqrmnopqr

Sample Output 4

26
1
2
3
4
16
6
4
1
6

Sample Input 5

1
a

Sample Output 5

0