#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,int z) {
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(sa,0,sizeof(sa));
memset(rnk,0,sizeof(rnk));
memset(tmp,0,sizeof(tmp));
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]] = k;
k = max(k - 1, 0);
}
}
vector<int> lcp_construction(string const& s, vector<int> const& p) {
int n = s.size();
vector<int> rank(n, 0);
for (int i = 0; i < n; i++)
rank[p[i]] = i;
int k = 0;
vector<int> lcp(n-1, 0);
for (int i = 0; i < n; i++) {
if (rank[i] == n - 1) {
k = 0;
continue;
}
int j = p[rank[i] + 1];
while (i + k < n && j + k < n && s[i+k] == s[j+k])
k++;
lcp[rank[i]] = k;
if (k)
k--;
}
return lcp;
}
int query(int l,int r){
if(l>r)swap(l,r);
int res=INT_MAX;
for(int i=l;i<r;i++)res=min(res,lcp[i]);
return res;
}
void solve(){
string s;
int n;
cin>>s;
n=s.size();
suffix_array(n,s);
//lcp_array(n,s);
vector<int> p;
for(int i=0;i<n;i++)p.push_back(sa[i]);
auto x = lcp_construction(s,p);
for(int i=0;i<n-1;i++)lcp[i]=x[i];
//build(n,lcp);
for(int i=0;i<n;i++)invsa[sa[i]]=i;
//for(int i=0;i<n;i++)cout<<sa[i]<<" "<<lcp[i]<<"\n";
int last=0,ans=0;
for(int i=0;i<s.size()/2;i++){
if(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;
}
