1.

/*
* ACM Contest training
* Problem: 10617 - Again Palindrome
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=18&problem=1558
*
* @author Christoph Goettschkes
* @version 1.0, 01/06/2011
*
* Method : Add-hoc
* Status : Accepted
* Runtime: 0.228
*/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;

class Main
{
static HashMap<String, Long> cache = new HashMap<String, Long>();

public static void main(String[] args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(reader.readLine());
while(tc-- > 0) {

String input = reader.readLine();
if (input.length() == 0) {
tc++;
continue;
}

cache.clear();
System.out.println(test(input));
}
}

static long test(String s) {
if (s.length() == 0 || s.length() == 1)
return s.length();

if (s.length() == 2) {
if (s.charAt(0) == s.charAt(s.length() - 1))
return 3;
return 2;
}

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

long n = (s.charAt(0) != s.charAt(s.length() - 1)) ? -test(s.substring(1, s.length() - 1)) : 1;
n += test(s.substring(0, s.length() - 1)) + test(s.substring(1));

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


}



2.
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));
}
}
}