#include <bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for (long long i = (a), _b = (b); i <= _b; i++)
#define FORD(i,b,a) for (long long i = (b), _a = (a); i>= _a; i--)
#define REP(i,n) for( long long i = 0, _n = (n); i < _n; i++)
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MASK(i) (1<<(i))
#define BIT(x,i) ((x) >> (i) & 1)
using namespace std;
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if (x > y) {
x = y;
return true;
} else return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
} else return false;
}
const int N = 1e6+5;
const int base = 256;
int mod[2] = {(int)1e9+7,(int)998244353};
int pw[2][N], HASH[2][N];
unsigned getHash(int l,int r){
int u = (HASH[0][r] - HASH[0][l-1] * pw[0][r-l+1] + mod[0] * mod[0]) % mod[0];
int v = (HASH[1][r] - HASH[1][l-1] * pw[1][r-l+1] + mod[1] * mod[1]) % mod[1];
//cout << u << ' ' << v << '\n';
return (u << 30ll) | v;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int t;
cin >> t;
pw[0][0] = 1; pw[1][0] = 1;
FOR(i,1,N-1) pw[0][i] = pw[0][i-1] * base % mod[0], pw[1][i] = pw[1][i-1] * base % mod[1];
while(t--){
string s;
cin >> s;
int n = s.size();
if(n <= 15){
int ans = 0;
REP(mask, MASK(n)){
string t="";
vector<string> ok;
REP(i,n) {
t += s[i];
if(BIT(mask,i)){
ok.push_back(t);
t = "";
}
}
if(t.size()) ok.push_back(t);
int m = ok.size();
bool palin = true;
int i = 0, j = m - 1;
while(i <= j){
if(ok[i] != ok[j]) palin = false;
i++;j--;
}
if(palin) {
maximize(ans,m);
}
}
cout << ans << '\n';
continue;
}
s = " " + s;
FOR(i,1,n) HASH[0][i] = (HASH[0][i-1] * base + s[i]) % mod[0];
FOR(i,1,n) HASH[1][i] = (HASH[1][i-1] * base + s[i]) % mod[1];
int i = 1, j = n;
int ans = 0;
while(i < j){
int u = i, v = j;
while(getHash(i,u) != getHash(v,j) && u < n && v > 1) u++, v--;
if(i != v && u != j) ans += 2; else ans++;
i = u+1, j = v-1;
if(i == j) {
ans ++;
break;
}
}
cout << ans << '\n';
}
cerr << "\nTime elapsed: " << clock() * 1.000 / CLOCKS_PER_SEC << " ms.\n";
return 0;
}
