#include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; #define X first #define Y second #define SZ(x) int(x.size()) mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const int MXN = 1e6+5; ll pw[2][MXN], mod[2] = {1000000007, 998244353}; bool is_prime(int x) { for(int i=2; i*i<=x; i++) if(x%i == 0) return 0; return 1; } void gen_hash() { for(int t=0; t<2; t++) { pw[t][0] = 1; pw[t][1] = rng()%100 + 50; while(pw[t][1] == pw[t^1][1] || !is_prime(pw[t][1])) pw[t][1]++; for(int i=2; i<MXN; i++) pw[t][i] = pw[t][i-1]*pw[t][1] % mod[t]; } } struct Hash { ll h[2][MXN]; void init(string s) { for(int t=0; t<2; t++) { h[t][0] = 0; for(int i=1; i<SZ(s); i++) h[t][i] = (h[t][i-1]*pw[t][1] + s[i]) % mod[t]; } } pll get(int l, int r) { return { (h[0][r] - h[0][l-1]*pw[0][r-l+1]%mod[0] + mod[0]) % mod[0], (h[1][r] - h[1][l-1]*pw[1][r-l+1]%mod[1] + mod[1]) % mod[1] }; } } H; int32_t main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); gen_hash(); int t; cin >> t; while(t--) { string s; cin >> s; int n = SZ(s); s = "#" + s; H.init(s); int l=1, ans = 0; for(int r=1; r<=n/2; r++) if(H.get(l, r) == H.get(n+1-r, n+1-l)) { ans += 2; l = r+1; } ans += l<=n+1-l; cout << ans << '\n'; } return 0; }