#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

long long int search(int from, int to, const char* str, vector< vector<long long int> >& mem) {
  // [from, to)
  if (from == to || to-from == 1)
    return 1;

  if (mem[from][to] == -1) {
    long long int n = 0;
    if (str[from] != str[to-1] || (to-from)%2 == 0) {
      n = 0;
    }
    else {
      for(int i = from+1; i < to; i++) {
	if (str[i] == str[from]) {
	  // [from+1, ] subtree
	  // [i, len-i]
	  n = n + search(from+1, i, str, mem)*search(i, to, str, mem);
	  n = n % 1000000000;
	}
      }
    }
    mem[from][to] = n;
  }

  return mem[from][to];
}


int main() {
  ifstream fin("pyramids.in");
  int nCases;
  fin >> nCases;
  for(int iCase = 0; iCase < nCases; iCase++) {
    string s;
    fin >> s;
    int len = s.size();
    vector< vector<long long int> > mem(len+1, vector<long long int>(len+1, -1));
    long long int result = search(0, len, s.c_str(), mem);
    cout << result << endl;
  }
  return 0;
}