Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

In Chefland, each person has their own non-empty personal string. When two people with personal strings $T_{1}$ and $T_{2}$ (possibly identical) become friends in Chefland, their strings are replaced by a new string $S = T_{1} + T_{1} + T_{2} + T_{2}$, where $+$ denotes string concatenation.

Chef recently became friends with Chefina. However, Chefina's personal string was her favourite and she got upset when it was replaced by $S$. She wanted her personal string back. Chef does not remember $T_{1}$ and $T_{2}$ now, he only knows $S$.

Find the number of ways in which Chef can retrieve valid strings $T_{1}$ and $T_{2}$ from the given string $S$. It is also possible that Chef does not remember $S$ correctly, in which case there is no way to retrieve $T_{1}$ and $T_{2}$.

------  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 ways to retrieve $T_{1}$ and $T_{2}$ from $S$.

------  Constraints ------
$1 ≤ T ≤ 10^{4}$
$4 ≤ |S| ≤ 10^{5}$
$|S|$ is divisible by $2$
$S$ contains only lowercase English letters
the sum of $|S|$ over all test cases does not exceed $2 \cdot 10^{6}$

----- Sample Input 1 ------ 
3

abcd

aaaa

ababcdccdc
----- Sample Output 1 ------ 
0

1

1
----- explanation 1 ------ 
Example case 1: There is no way to choose $T_{1}$ and $T_{2}$.

Example case 2: Both $T_{1}$ and $T_{2}$ must be "a".

Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
for i in range(int(input())):
	s = input()
	c = 0
	l = len(s)
	for i in range(2, l, 2):
		a = i
		b = l - i
		t11 = s[0:a // 2]
		t12 = s[a // 2:a]
		t21 = s[a:a + b // 2]
		t22 = s[a + b // 2:]
		if t11 == t12 and t21 == t22:
			c = c + 1
	print(c)


T = int(input())
for i in range(T):
	S = input()
	C = 0
	l = len(S)
	for i in range(2, l, 2):
		a = i
		b = l - i
		T11 = S[0:a // 2]
		T12 = S[a // 2:a]
		T21 = S[a:a + b // 2]
		T22 = S[a + b // 2:]
		if T11 == T12 and T21 == T22:
			C = C + 1
	print(C)


for i in range(int(input())):
	S = input()
	T = 0
	l = len(S)
	for i in range(2, l, 2):
		x = i
		y = l - i
		T1 = S[0:x // 2]
		T2 = S[x // 2:x]
		T3 = S[x:x + y // 2]
		T4 = S[x + y // 2:]
		if T1 == T2 and T3 == T4:
			T = T + 1
	print(T)


x = int(input())
for j in range(x):
	s = input()
	n = len(s)
	count = 0
	for i in range(2, n - 1, 2):
		if s[:i // 2] == s[i // 2:i] and s[i:i + (n - i) // 2] == s[i + (n - i) // 2:n]:
			count += 1
	print(count)


for i in range(int(input())):
	s = input()
	c = 0
	l = len(s)
	for i in range(2, l, 2):
		a = i
		b = l - i
		p11 = s[0:a // 2]
		p12 = s[a // 2:a]
		p21 = s[a:a + b // 2]
		p22 = s[a + b // 2:]
		if p11 == p12 and p21 == p22:
			c = c + 1
	print(c)


for _ in range(int(input())):
	s = input()
	n = len(s)
	count = 0
	for i in range(2, n - 1, 2):
		if s[:i // 2] == s[i // 2:i] and s[i:i + (n - i) // 2] == s[i + (n - i) // 2:n]:
			count += 1
	print(count)


for i in range(int(input())):
	r = input()
	k = 0
	l = len(r)
	for i in range(2, l, 2):
		a = i
		b = l - i
		t11 = r[0:a // 2]
		t12 = r[a // 2:a]
		t21 = r[a:a + b // 2]
		t22 = r[a + b // 2:]
		if t11 == t12 and t21 == t22:
			k = k + 1
	print(k)


for i in range(int(input())):
	sp = input()
	c = 0
	lp = len(sp)
	for i in range(2, lp, 2):
		ap = i
		bp = lp - i
		t11 = sp[0:ap // 2]
		t12 = sp[ap // 2:ap]
		t21 = sp[ap:ap + bp // 2]
		t22 = sp[ap + bp // 2:]
		if t11 == t12 and t21 == t22:
			c = c + 1
	print(c)


for _ in range(int(input())):
	r = input()
	h = len(r)
	count = 0
	for i in range(2, h - 1, 2):
		if r[:i // 2] == r[i // 2:i] and r[i:i + (h - i) // 2] == r[i + (h - i) // 2:h]:
			count += 1
	print(count)