#include <bits/stdc++.h>
#define N 1005
#define MOD 10007
using namespace std;
int memo[N][N][2];
char s[N];
int DP(int ini, int fin, int flag){
if(ini > fin)return 1;
if(ini == fin){
if(flag == 0)return 1;
return 2;
}
int &ret = memo[ini][fin][flag];
if(ret != -1)return ret;
long long ans = 0;
if(s[ini] == s[fin]){
ans += DP(ini + 1, fin - 1, 1);
ans += DP(ini + 1, fin, flag);
ans += DP(ini, fin - 1, flag);
if(ini + 1 < fin)ans -= DP(ini + 1, fin - 1, flag);
}
else{
ans += DP(ini + 1, fin, flag);
ans += DP(ini, fin - 1, flag);
if(ini + 1 < fin)ans -= DP(ini + 1, fin - 1, flag);
}
if(ans >= MOD)ans %= MOD;
if(ans < 0)ans += MOD;
return ret = ans;
}
int main() {
int tc = 0;
scanf("%d", &tc);
while(tc--){
scanf("%s", &s);
int n = strlen(s);
memset(memo, -1, sizeof memo);
int ans = DP(0, n - 1, 0);
printf("%d\n", ans);
}
}
CiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgojZGVmaW5lIE4gMTAwNQoKI2RlZmluZSBNT0QgMTAwMDcKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWVtb1tOXVtOXVsyXTsKY2hhciBzW05dOwoKaW50IERQKGludCBpbmksIGludCBmaW4sIGludCBmbGFnKXsKCQoJaWYoaW5pID4gZmluKXJldHVybiAxOwoJaWYoaW5pID09IGZpbil7CgkJCgkJaWYoZmxhZyA9PSAwKXJldHVybiAxOwoJCXJldHVybiAyOwoJfQoJCglpbnQgJnJldCA9IG1lbW9baW5pXVtmaW5dW2ZsYWddOwoJCglpZihyZXQgIT0gLTEpcmV0dXJuIHJldDsKCWxvbmcgbG9uZyBhbnMgPSAwOwoJCglpZihzW2luaV0gPT0gc1tmaW5dKXsKCQkKCQlhbnMgKz0gRFAoaW5pICsgMSwgZmluIC0gMSwgMSk7CgkJYW5zICs9IERQKGluaSArIDEsIGZpbiwgZmxhZyk7CgkJYW5zICs9IERQKGluaSwgZmluIC0gMSwgZmxhZyk7CgkJaWYoaW5pICsgMSA8IGZpbilhbnMgLT0gRFAoaW5pICsgMSwgZmluIC0gMSwgZmxhZyk7CgkJCgl9CgllbHNlewoJCQoJCWFucyArPSBEUChpbmkgKyAxLCBmaW4sIGZsYWcpOwoJCWFucyArPSBEUChpbmksIGZpbiAtIDEsIGZsYWcpOwoJCWlmKGluaSArIDEgPCBmaW4pYW5zIC09IERQKGluaSArIDEsIGZpbiAtIDEsIGZsYWcpOwoJCQoJfQoJCglpZihhbnMgPj0gTU9EKWFucyAlPSBNT0Q7CglpZihhbnMgPCAwKWFucyArPSBNT0Q7CgkKCXJldHVybiByZXQgPSBhbnM7Cn0KCmludCBtYWluKCkgewoJCglpbnQgdGMgPSAwOwoJc2NhbmYoIiVkIiwgJnRjKTsKCQoJd2hpbGUodGMtLSl7CgkJCgkJc2NhbmYoIiVzIiwgJnMpOwoJCWludCBuID0gc3RybGVuKHMpOwoJCQoJCW1lbXNldChtZW1vLCAtMSwgc2l6ZW9mIG1lbW8pOwoJCQkKCQkJCgkJaW50IGFucyA9IERQKDAsIG4gLSAxLCAwKTsKCQlwcmludGYoIiVkXG4iLCBhbnMpOwoJCQoJfQoJCn0KCgo=