#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1000000;
const int M = N * 2 + 1;
char cc[N + 1], cc_[M];
int rr[M];
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
int t; cin >> t;
while (t--) {
cin >> cc;
int n = strlen(cc), m = 0; cc_[m++] = ' ';
for (int i = 0, j = n - 1; i < j; i++, j--) {
cc_[m++] = cc[i];
cc_[m++] = ' ';
cc_[m++] = cc[j];
cc_[m++] = ' ';
}
for (int o = 0, i = 0, j = 0; i < m; i++)
if (o * 2 - i >= 0 && i + rr[o * 2 - i] < j)
rr[i] = rr[o * 2 - i];
else {
j = max(j, (o = i) + 1);
while (0 <= o * 2 - j && j < m && cc_[j] == cc_[o * 2 - j])
j++;
rr[i] = j - o;
}
int k = 0, i_ = 0;
for (int i = 2; i <= n; i += 2)
if (rr[i_ + i] > i - i_)
k += 2, i_ = i;
if (i_ < n)
k++;
cout << k << '\n';
}
return 0;
}
