Read problems statements in Mandarin Chinese  , Russian and Vietnamese 

Divyam is teaching his student Amit about palindromes. A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward. For example, the string “abcba” is a palindrome. After teaching about it, Divyam gave a puzzle for Amit to solve:

Given a string S. Find the number of positions in S where we can insert a character to convert it into a palindrome. Character can be inserted in the beginning or the end, so there will be (N+1) possible positions for the insertion in a string having original length N. For example, if S = “aaa”, then there are four positions where we can insert a character so that the converted string is a palindrome. Converted palindromes are “aaaa”, “aaaa”, “aaaa” and “aaaa”. Inserted character is shown in boldface.

Amit finds the puzzle too difficult. Can you help him in solving it?

------ Input ------ 

First line of input contains an integer T denoting the number of test cases.
First line of each test case will contain a string S containing lowercase letters only. 

------ Output ------ 

Print T lines, each containing an integer: the solution for the corresponding test case.

------ Constraints ------ 

Subtask #1: 20 points

	$1 ≤ T  ≤ 5, 1 ≤ length of string ≤ 1000$

Subtask #2: 80 points

	$1 ≤ T  ≤ 5,  1 ≤ length of string ≤ 10^{5}$

----- Sample Input 1 ------ 
2

aaa

aca
----- Sample Output 1 ------ 
4

2
----- explanation 1 ------ 

First sample has been explained in the problem statement.

Source: codechef | Difficulty: VERY_HARD
Tags: String algorithms


Solutions:
def equi(i, y, l):
	c = 0
	if i == 0:
		return c
	for x in range(1, i + 1):
		if y != l[i - x]:
			break
		c = c + 1
	return c

def palindrome(s):
	n = len(s)
	for i in range(int(n / 2)):
		if s[i] != s[n - 1 - i]:
			return (False, i)
	return (True,)

def positions(s):
	n = len(s)
	if n % 2 != 0:
		m = int((n - 1) / 2)
		t = palindrome(s)
		if t[0]:
			r = equi(m, s[m], s) + 1
			return (r, r)
		else:
			l = 0
			r = 0
			if s[m - 1] == s[m]:
				if palindrome(s[t[1]:n - 1 - t[1]])[0]:
					l = equi(t[1], s[n - 1 - t[1]], s) + 1
			if s[m] == s[m + 1]:
				s2 = s[n - 1::-1]
				t1 = palindrome(s2)[1]
				if palindrome(s2[t1:n - t1 - 1])[0]:
					r = equi(t1, s2[n - 1 - t1], s2) + 1
		return (l, r)
	else:
		m = int(n / 2)
		if palindrome(s)[0]:
			r = equi(m, s[m], s)
			return (r, r + 1)
		if s[m - 1] == s[m]:
			s1 = s[:m] + s[m + 1:]
			return positions(s1)
		else:
			s2 = s[:m - 1] + s[m:]
			s3 = s[:m] + s[m + 1:]
			return (positions(s2)[0], positions(s3)[1])
t = int(input())
r = []
for i in range(t):
	s = input()
	q = positions(s)
	r = r + [q[0] + q[1]]
for i in range(t):
	print(r[i])