1. 
import java.io.*;
import java.util.*;

class Main {

private static HashMap<String,Long> cache = new HashMap<String, Long>();

static long solve(String s)
{
if(s.length() == 0)
return 0;

if(s.length() == 1)
return 1;

if(s.length() == 2)
return (s.charAt(0) == s.charAt(1))? 3:2;

if(cache.containsKey(s))
return cache.get(s);

long sum = 0;
int end = s.length()-1;

if(s.charAt(0) == s.charAt(end))
sum += 1 + solve(s.substring(1,end));

sum += solve(s.substring(1,end+1));
sum += solve(s.substring(0,end));
sum -= solve(s.substring(1,end));

cache.put(s,sum);
return sum;
}

public static void main(String... args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String input;
int cases = Integer.parseInt(reader.readLine());

for(int c = 0; c < cases; c++)
{
cache.clear();
input = reader.readLine();
System.out.println(solve(input));
}
}
}