https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1558
#include <bits/stdc++.h>
#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)
using namespace std;
string s;
const int MAX = 61;
ll cache[MAX][MAX];
ll nWays(int st, int en) {
if(st == en)
return 1;
if(st+1 == en) {
return 2 + (s[st] == s[en]);
}
ll &ret = cache[st][en];
if(ret != -1)
return ret;
ret = 0;
if(s[st] == s[en])
ret += nWays(st+1, en-1) + 1;
ret += nWays(st, en-1);
ret += nWays(st+1, en);
ret -= nWays(st+1, en-1);
return ret;
}
int main() {
int t;
cin>>t;
while(t--) {
clr(cache, -1);
cin>>s;
cout << nWays(0, s.length()-1) << endl;
}
return 0;
}