#include <bits/stdc++.h> #define ll long long using namespace std; const int T = 6e6 + 10; string s[20]; int t; namespace full{ const int P[] = {301, 293}; const int MOD[] = {(ll)1e9 + 7, 998'244'353}; ll Pow[2][T], hsh[2][T]; bool sub(){ return 1; } ll hashing(int l, int r) { int u = (hsh[0][r] - hsh[0][l-1] * Pow[0][r - l + 1] + 1ll * MOD[0] * MOD[0]) % MOD[0]; int v = (hsh[1][r] - hsh[1][l-1] * Pow[1][r - l + 1] + 1ll * MOD[1] * MOD[1]) % MOD[1]; return 1ll * u * MOD[1] + v; } int calc(string &s) { int n = s.size(); Pow[0][0] = Pow[1][0] = 1; hsh[0][0] = hsh[1][0] = 0; for(int i = 1; i <= n; ++i) { Pow[0][i] = Pow[0][i-1] * P[0] % MOD[0]; Pow[1][i] = Pow[1][i-1] * P[1] % MOD[1]; hsh[0][i] = (hsh[0][i-1] * P[0] + s[i-1]) % MOD[0]; hsh[1][i] = (hsh[1][i-1] * P[1] + s[i-1]) % MOD[1]; } int res = 0, l = 1, r = n; for(int i = 1; i < n - i + 1; ++i){ // cout << l << ' ' << i << ' ' << n - i + 1 << ' ' << r << '\n'; if(hashing(l, i) == hashing(n - i + 1, r)) { res += 2; l = i + 1; r = n - i; } } res += (l <= r); return res; } void solve(){ for(int i = 1; i <= t; ++i){ cout << calc(s[i]) << '\n'; } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> t; for(int i = 1; i <= t; ++i) cin >> s[i]; if(full::sub()) return full::solve(), 0; return 0; }