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

int main() {
  int N; cin>>N; string dummy; getline(cin,dummy);

  while(N--) {
    string Tape; getline(cin,Tape);

    long long dp[300][300]={0}; // dp[a][n]: the number of cases from [a,a+n]
    for(int a=0; a<Tape.size(); ++a)
      dp[a][0] = 1;
    for(int n=2; n<Tape.size(); n+=2)
      for(int a=0; a+n<Tape.size(); ++a)
        if( Tape[a] == Tape[a+n] )
          for(int k=0; k<n; k+=2)
            dp[a][n] = (dp[a][n] + dp[a][k]*dp[a+k+1][n-k-2]) % 1000000000;

    cout << dp[0][Tape.size()-1] << endl;
  }
}