//GNC

#include<iostream>
#include<string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <fstream>
#include <sstream>

using namespace std;
const long long modulo=1000000000;
map<string , long long > table;

long long f(const string &s, int begin, int end)
{
  if ( end-begin<=0 ) return 0;
  if ( end-begin==1 ) return 1;
  if ( s[begin]!=s[end-1] ) return 0;
  
  if ( table.count(string(s, begin,end-begin)) ) {
    return table[string(s, begin, end-begin)];
  }
  
  long long ret=0;
  
  char fst=s[begin];
  for ( int i=begin+1 ; i<end ; i++ ) {
    if ( s[i]!=fst ) continue;
    /*&
cout<<"f("<<string(s,begin,end)<<")="
	<<ret<<"+ f("<<string(s,begin+1,i)<<")*f("
	<<string(s,i,end)<<")"<<endl;
    */
    long long t=f(s, begin+1, i) * f(s, i, end);
    t%=modulo;
    ret+=t;
    ret%=modulo;
  }
  
  return table[string(s,begin,end-begin)]=ret;
}

int main(void){
  ifstream cin("pyramids.in");
  int ncases;
  cin>>ncases;
  while ( --ncases>=0 ) {
    string s;
    cin>>s;
    cout<<f(s, 0, s.length())<<endl;
  }
  /*for ( map<string, long long>::iterator it=table.begin();
	it!=table.end() ; ++it ) {
    cout<<"f("<<it->first<<")="<<it->second<<endl;
    }*/
  return 0;
}