#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1 << 20, LOGN = 21;
int table[LOGN][MAXN];
void build(int N, int* V) {
copy(V, V + N, table[0]);
for (int j = 1; j < LOGN; j++) {
for (int i = 0; i + (1 << j) <= N; i++) {
table[j][i]=min(table[j-1][i],
table[j-1][i+(1<<j)/2]);
}
}
}
int query(int l, int r) {
if(l>r)swap(l,r);
int k = 31 - __builtin_clz(r - l); // [l, r)
return min(table[k][l], table[k][r-(1 << k)]);
}
int sa[MAXN], rnk[2*MAXN], lcp[MAXN], tmp[MAXN], invsa[MAXN];
void suffix_array(int N, const string& S) {
memset(rnk,0,sizeof(rnk));
for (int i = 0; i < N; i++) {
sa[i] = i, rnk[i] = S[i];
}
for (int k = 1; k < N; k *= 2) {
sort(sa, sa + N, [&](int a, int b) {
return tie(rnk[a],rnk[a+k]) < tie(rnk[b],rnk[b+k]);
});
tmp[sa[0]] = 1;
for (int i = 1; i < N; i++) {
tmp[sa[i]] = tmp[sa[i-1]] + (rnk[sa[i]] !=
rnk[sa[i-1]] || rnk[sa[i]+k] != rnk[sa[i-1]+k]);
}
copy(tmp, tmp + N, rnk);
if (rnk[sa[N - 1]] == N) break;
}
}
void lcp_array(int N, const string& S) {
for (int i = 0, k = 0; i < N; i++) {
int j = sa[rnk[i]];
while (i+k < N && j+k < N && S[i+k] == S[j+k]) k++;
lcp[rnk[i] - 1] = k;
k = max(k - 1, 0);
}
}
void solve(){
string s;
int n;
cin>>s;
n=s.size();
suffix_array(n,s);
lcp_array(n,s);
build(n-1,lcp);
for(int i=0;i<n;i++)invsa[sa[i]]=i;
int last=0,ans=0;
for(int i=0;i<s.size()/2;i++){
if(s[last]==s[s.size()-1-i] && query(invsa[last],invsa[s.size()-1-last-(i-last)])>=(i-last+1)){
last=i+1;
ans+=2;
}
}
if(last!=s.size()/2 || s.size()%2==1)ans++;
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}
