Read problems statements in Mandarin chinese and Vietnamese as well. 

You are given a string $S$. A cyclic shift of $S$ is a string formed by moving a number of characters from the beginning of $S$ to its end (in the same order). Formally, for an integer $k$ ($0 ≤ k < N$), the $k$-th cyclic shift is a string $R$ with length $N$ such that:
$R_{i} = S_{i+k}$ for each $1 ≤ i ≤ N-k$
$R_{i} = S_{i-N+k}$ for each $N-k+1 ≤ i ≤ N$

A string is palindromic if it is equal to its own reverse string.

Compute the number of palindromic cyclic shifts of the given string.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single string $S$.

------  Output ------
For each test case, print a single line containing one integer — the number of palindromic shifts.

------  Constraints  ------
$1 ≤ T ≤ 1,000$
$1 ≤ |S| ≤ 2\cdot 10^{5}$
$|S|$ contains only lowercase English letters
the sum of $|S|$ in all test cases does not exceed $2\cdot 10^{5}$

------  Subtasks ------
Subtask #1 (20 points): the sum of $|S|$ in all test cases does not exceed $100$

Subtask #2 (20 points): the sum of $|S|$ in all test cases does not exceed $5,000$

Subtask #3 (60 points): original constraints

----- Sample Input 1 ------ 
1
aabb
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
Example case 1: The two palindromic cyclic shifts of "aabb" are "abba" and "baab".

Source: codechef | Difficulty: HARD
Tags: String algorithms

Data structures


Solutions:
t = int(input())
M = 1000000007
mul = [1]
for i in range(4 * 100000):
	mul.append(mul[-1] * 101 % M)
while t:
	t -= 1
	a = input()
	n = len(a)
	a += a
	pre = [0]
	for i in range(1, 2 * n + 1):
		pre.append((pre[-1] + ord(a[i - 1]) * mul[i - 1] % M) % M)
	suf = [0]
	for i in range(2 * n, 0, -1):
		suf.append((suf[-1] + ord(a[i - 1]) * mul[2 * n - i] % M) % M)
	ans = 0
	for i in range(n):
		if (pre[n + i] - pre[i] + M) % M * mul[n - i] % M == (suf[2 * n - i] - suf[n - i] + M) % M * mul[i] % M:
			ans += 1
	print(ans)


m = 1000000007
t = int(input())
p2 = []
p2.append(1)
for i in range(400000):
	p2.append(p2[i] * 31 % m)
for h in range(t):
	s = input()
	n = len(s)
	s2 = s[::-1]
	hash1 = 0
	hash2 = 0
	for i in range(n):
		hash1 += p2[i] * (ord(s[i]) - ord('a'))
		hash1 %= m
		hash2 += p2[i] * (ord(s2[i]) - ord('a'))
		hash2 %= m
	ans = 0
	for i in range(n):
		hash1 -= p2[i] * (ord(s[i]) - ord('a'))
		hash1 += p2[i + n] * (ord(s[i]) - ord('a'))
		hash1 %= m
		if hash1 < 0:
			hash1 += m
		hash2 *= p2[2]
		hash2 %= m
		hash2 -= p2[n + 1 + i] * (ord(s2[n - 1 - i]) - ord('a'))
		hash2 += p2[i + 1] * (ord(s2[n - 1 - i]) - ord('a'))
		hash2 %= m
		if hash2 < 0:
			hash2 += m
		if hash1 == hash2:
			ans += 1
	print(ans)