#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;

int solve(int f,int t,string &s,vector<vector<int> > &v);

int split(int f,int t,string &s,vector<vector<int> > &v)
{
  if (f>t) return 1;
  if (f==t) return 0;
  if (v[f][t]>=0) return v[f][t];
  char c=s[t];
  int ret=0;
  for (int i=f+1;i<=t;i+=2)
    if (s[i]==c){
      long long tmp=(long long)ret+(long long)solve(f,i-1,s,v)*(long long)split(i+1,t,s,v);
      ret=(int)(tmp%1000000000);
    }
  return v[f][t]=ret;
}

int solve(int f,int t,string &s,vector<vector<int> > &v)
{
  if (f>t) return 0;
  if ((t-f)%2!=0) return 0;
  if (f==t) return 1;
  if (v[f][t]>=0) return v[f][t];
  char c=s[f];
  if (c!=s[t]) return v[f][t]=0;
  return v[f][t]=split(f+1,t,s,v);
}

int main()
{
  ifstream cin("pyramids.in");
  int cases;cin>>cases;
  while(cases--){
    string s;cin>>s;
    int n=s.length();
    if (n%2==0){
      cout<<0<<endl;
      continue;
    }
    vector<vector<int> > tbl(n,vector<int>(n,-1));
    cout<<solve(0,n-1,s,tbl)<<endl;
  }
  return 0;
}