#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; }; auto sub = [&](int l, int r) { string ret; l--; r--; for (int i = l; i <= r; i++) { ret += a[i]; } return ret; }; 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); string left = sub(tl, l); string right = sub(r, tr); if (left == right) { assert(pre == suf); } if (pre == suf) { assert(left == right); // string left = a.substr(a.begin() + tl - 1, a.begin() + l); // string right = a.substr(a.begin() + r - 1, a.begin() + tr); tl = l + 1; tr = r - 1; s.clear(); ans += 2; } l++; r--; } 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; }