#include<bits/stdc++.h> #define ll long long #define fi first #define se second #define ins insert #define pb push_back #define foru(i,a,b) for(int i=a;i<=b;i++) #define ford(i,a,b) for(int i=a;i>=b;i--) #define pii pair<int,int> #define pll pair<ll,ll> #define int ll using namespace std; int const mod=1e9+7,base=37; int nt,n; int hashx[1000006],f[1000006]; string x; ll gethash(int l,int r) { return (hashx[r]-hashx[l-1]*f[r-l+1]%mod+mod*2)%mod; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); // freopen(".inp","r",stdin); // freopen(".out","w",stdout); f[0]=1; for(int i=1;i<=1000000;i++) { f[i]=f[i-1]*base%mod; } cin>>nt; while(nt--) { cin>>x; n=x.size(); x=' '+x; for(int i=1;i<=n;i++) { hashx[i]=hashx[i-1]*base%mod+x[i]; hashx[i]%=mod; } int ans=0; int l=1,r=n; for(int i=1;i<=(n+1)/2;i++) { int leng=i-l+1; if(l+leng-1>=r-leng+1) break; if(gethash(l,l+leng-1)==gethash(r-leng+1,r)) { ans+=2; l=l+leng; r=r-leng; } } cout<<ans+(l<=r)<<'\n'; } } /* em thi cho du co khoc cung se den ngay phai quen thien duong van cho ngay em den */