#include <bits/stdc++.h> using namespace std; constexpr int p = 31; constexpr int mod = 1e9 + 7; void solve() { string a; cin >> a; int n = a.size(); vector<int> h(n + 1), pw(n + 1, 1); for (int i = 0; i < n; i++) { pw[i + 1] = (pw[i] * p) % mod; h[i + 1] = (h[i] * p + (a[i] - 'a' + 1)) % mod; } auto get = [&](int l, int r) { return (h[r] - h[l - 1] * pw[r - l + 1] % mod + mod) % mod; }; int tl = 1, tr = n, l = 1, r = n, ans = 0; string s; while (l < r) { s.push_back(a[l]); int pre = get(tl, l++); int suf = get(r--, tr); if (pre == suf) { tl = l; tr = r; s.clear(); ans += 2; } } if (l <= r || !s.empty()) { ans++; } cout << ans << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { solve(); } return 0; }