/**
* Source: own
* Description: Pairs reduce frequency of collision
* Verification: Dec 17 Plat 1
*/
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
template<typename T>
ostream& operator<< (ostream& out, const pair<T, T>& v) {
out << "{" << v.first << ", " << v.second << "}";
return out;
}
template<typename T>
ostream& operator<< (ostream& out, const vector<T>& v) {
out << "[";
size_t last = v.size() - 1;
for(size_t i = 0; i < v.size(); ++i) {
out << v[i];
if (i != last)
out << ", ";
}
out << "]";
return out;
}
template<typename T>
ostream& operator<< (ostream& out, const set<T>& v) {
out << "[";
auto pen = v.end();
pen--;
for (auto it = v.begin(); it != v.end(); it++){
out << *it;
if (it != pen){
out << ", ";
}
}
out << "]";
return out;
}
template<typename T>
ostream& operator<< (ostream& out, const Tree<T>& v) {
out << "[";
auto pen = v.end();
pen--;
for (auto it = v.begin(); it != v.end(); it++){
out << *it;
if (it != pen){
out << ", ";
}
}
out << "]";
return out;
}
typedef pair<ll, ll> pll;
template<class T> pair<T,T> operator+(const pair<T,T>& l, const pair<T,T>& r) {
return {(l.f+r.f)%MOD,(l.s+r.s)%MOD};
}
template<class T> pair<T,T> operator-(const pair<T,T>& l, const pair<T,T>& r) {
return {(l.f-r.f+MOD)%MOD,(l.s-r.s+MOD)%MOD};
}
template<class T> pair<T,T> operator*(const pair<T,T>& l, const T& r) {
return {l.f*r%MOD,l.s*r%MOD};
}
template<class T> pair<T,T> operator*(const pair<T,T>& l, const pair<T,T>& r) {
return {l.f*r.f%MOD,l.s*r.s%MOD};
}
struct hsh {
string S;
vector<pll> po, ipo, cum;
pll base = mp(948392576,573928192);
ll modpow(ll b, ll p) {
return !p?1:modpow(b*b%MOD,p/2)*(p&1?b:1)%MOD;
}
ll inv(ll x) {
return modpow(x,MOD-2);
}
void gen(string _S) {
S = _S;
po.resize(sz(S)), ipo.resize(sz(S)), cum.resize(sz(S)+1);
po[0] = ipo[0] = {1,1};
FOR(i,1,sz(S)) {
po[i] = po[i-1]*base;
ipo[i] = {inv(po[i].f),inv(po[i].s)};
}
F0R(i,sz(S)) cum[i+1] = cum[i]+po[i]*(ll)(S[i]-'a'+1);
}
pll get(int l, int r) {
return ipo[l]*(cum[r+1]-cum[l]);
}
};
int lcp(hsh& a, hsh& b) { // can be used to generate a suffix array
int lo = 0, hi = min(sz(a.S),sz(b.S));
while (lo < hi) {
int mid = (lo+hi+1)/2;
if (a.get(0,mid-1) == b.get(0,mid-1)) lo = mid;
else hi = mid-1;
}
return lo;
}
string s;
hsh h;
int solve(int idx){
if (s.size() % 2 == 1){
if (idx == s.size() / 2) return 1;
int res = 1;
for (int j = idx + 1; j <= s.size() / 2; j++){
if (h.get(idx, j - 1) == h.get(s.size() - j, s.size() - 1 - idx)){
return max(res, solve(j) + 2);
}
}
return res;
}
else{
if (idx == s.size() / 2) return 0;
int res = 1;
for (int j = idx + 1; j <= s.size() / 2; j++){
if (h.get(idx, j - 1) == h.get(s.size() - j, s.size() - 1 - idx)){
return max(res, solve(j) + 2);
}
}
return res;
}
}
int main() {
int T; cin >> T;
for (int testcase = 0; testcase < T; testcase++){
cin >> s;
h.gen(s);
cout << solve(0) << endl;
}
}
