#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll M = (1LL<<61)-1; mt19937 rng((ll)chrono::steady_clock::now().time_since_epoch().count()); const ll B = uniform_int_distribution<ll>(0, M - 1)(rng); ll mul(ll a, ll b){ return ( (__int128)a * b % M + M ) % M; } void solve(){ string s; cin>>s; int n = s.size(); vector<ll> p_hash(n+1, 0), pw(n+1, 1); for (int i=0;i<n;i++) pw[i+1] = mul(pw[i], B); for (int i=0;i<n;i++) p_hash[i+1] = (mul(p_hash[i], B) + s[i]) % M; auto hsh = [&](int l, int r){ ll val = (p_hash[r+1] - mul(p_hash[l], pw[r-l+1])) % M; return (val + M) % M; }; int l = 0, r = n-1; int ans = 0; while(l<=r){ if (l == r) { ans++; break; } int nl=l, nr=r; while(nl < nr){ // [l;nl] =?= [nr;r] if (hsh(l, nl) == hsh(nr, r)) break; nl++; nr--; } if (nl >= nr) { ans++; break; } else { l = nl+1; r = nr-1; ans += 2; } } cout << ans << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int tt=1; cin>>tt; while(tt--) solve(); }