#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1 << 20, LOGN = 21;
int table[LOGN][MAXN];
void build(int N, vector<int> &V) {
copy(V.begin(), V.begin()+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)]);
}
template<class T> using V = vector<T>;
using vi = V<int>;
#define sz(x) int((x).size())
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define each(a,x) for (auto& a: x)
#define all(x) begin(x), end(x)
string S; int N; vi sa, isa, lcp;
struct SuffixArray {
void init(string _S) { N = sz(S = _S)+1; genSa(); genLcp(); }
void genSa() { // sa has size sz(S)+1, starts with sz(S)
sa = isa = vi(N); sa[0] = N-1; iota(1+all(sa),0);
sort(1+all(sa),[&](int a, int b) { return S[a] < S[b]; });
FOR(i,1,N) { int a = sa[i-1], b = sa[i];
isa[b] = i > 1 && S[a] == S[b] ? isa[a] : i; }
for (int len = 1; len < N; len *= 2) { // currently sorted
// by first len chars
vi s(sa), is(isa), pos(N); iota(all(pos),0);
each(t,s) {int T=t-len;if (T>=0) sa[pos[isa[T]]++] = T;}
FOR(i,1,N) { int a = sa[i-1], b = sa[i]; /// verify that nothing goes out of bounds
isa[b] = is[a]==is[b]&&is[a+len]==is[b+len]?isa[a]:i; }
}
}
void genLcp() { // Kasai's Algo
lcp = vi(N-1); int h = 0;
F0R(b,N-1) { int a = sa[isa[b]-1];
while (a+h < sz(S) && S[a+h] == S[b+h]) ++h;
lcp[isa[b]-1] = h; if (h) h--; }
//R.init(lcp); /// if we cut off first chars of two strings
/// with lcp h then remaining portions still have lcp h-1
}
/*RMQ<int> R;
int getLCP(int a, int b) { // lcp of suffixes starting at a,b
if (a == b) return sz(S)-a;
int l = isa[a], r = isa[b]; if (l > r) swap(l,r);
return R.query(l,r-1);
}*/
};
int invsa[MAXN];
void solve(){
string s;
int n;
cin>>s;
n=s.size();
SuffixArray tmp;
tmp.init(s);
//suffix_array(n,s);
//lcp_array(n,s);
build(n,lcp);
for(int i=0;i<=n;i++){
invsa[sa[i]]=i;
//cout<<sa[i]<<" "<<lcp[i]<<"gg\n";
}
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;
}
