subpalindrome-2

For every string given as input, you need to tell us the number of subsequences of it that are palindromes (need not necessarily be distinct). Note that the empty string is not a palindrome. 

SAMPLE INPUT
1
aab

SAMPLE OUTPUT
4

Explanation

the palindromic subsequences of "aab" are:
"a", "a", "b", "aa", and the method returns 4.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
t=eval(input())

paliCount=[[]]

def cPalis(s,i,j):
	if j<i: return 0
	if i==j: return 1
	if paliCount[i][j]: return paliCount[i][j]
	su=cPalis(s,i,j-1)
	for k in range(i,j+1):
		if s[k]==s[j]: 
			su+=1+cPalis(s,k+1,j-1)
			#print k,j,s[k],s[j]
	return su	

for _ in range(t):
	s=input()
	n=len(s)
	paliCount=[[0]*n for i in range(n)]
	r=cPalis(s,0,n-1)
	print(r)
	#print filter(lambda x: x,cnt),filter(lambda x: x,found)