#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1000000;
const int N_ = 1 << 20;
const int INF = 0x3f3f3f3f;
char cc[N + 1];
int sa[N], aa0[N], aa1[N], tt[N], kk[N + 2], st[N_ << 1], n_;
void compress(int n) {
for (int a = 0, h = 0; h < n; h++)
aa0[sa[h]] = h + 1 == n || aa0[sa[h]] < aa0[sa[h + 1]] || aa1[sa[h]] < aa1[sa[h + 1]] ? a++ : a;
}
void extend(int n, int m) {
for (int i = 0; i < n; i++)
aa1[i] = i + m < n ? aa0[i + m] : -1;
}
void sort(int *ii, int *jj, int *aa, int n) {
for (int a = 0; a < n + 2; a++)
kk[a] = 0;
for (int i = 0; i < n; i++)
kk[aa[i] + 2]++;
for (int a = 1; a < n + 2; a++)
kk[a] += kk[a - 1];
for (int h = 0; h < n; h++)
jj[kk[aa[ii[h]] + 1]++] = ii[h];
}
int query(int l, int r) {
int x = INF;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if (l & 1)
x = min(x, st[l++]);
if (!(r & 1))
x = min(x, st[r--]);
}
return x;
}
int lcp(int i, int j) {
int a = aa0[i], b = aa0[j];
if (a > b)
swap(a, b);
return query(a, b - 1);
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
int t; cin >> t;
while (t--) {
cin >> cc;
int n = strlen(cc);
for (int a = 0; a < n; a++)
sa[a] = a;
sort(sa, sa + n, [] (int i, int j) { return cc[i] < cc[j]; });
for (int i = 0; i < n; i++)
aa0[i] = cc[i], aa1[i] = 0;
compress(n);
for (int m = 1; m < n; m <<= 1) {
extend(n, m);
sort(sa, tt, aa1, n);
sort(tt, sa, aa0, n);
compress(n);
}
n_ = 1;
while (n_ < n - 1)
n_ <<= 1;
for (int l = 0, i = 0; i < n; i++, l = max(l - 1, 0)) {
int a = aa0[i];
if (a + 1 < n) {
for (int j = sa[a + 1]; i + l < n && cc[i + l] == cc[j + l]; l++)
;
st[a + n_] = l;
}
}
for (int i = n_ - 1; i; i--) {
int l = i << 1, r = l ^ 1;
st[i] = min(st[l], st[r]);
}
int k = 0;
for (int i = 0, j; i < n / 2; i = j, k += 2) {
for (j = i + 1; j <= n / 2 && lcp(i, n - j) < j - i; j++)
;
if (j > n / 2) {
k++;
break;
}
}
if (n % 2 && k % 2 == 0)
k++;
cout << k << '\n';
}
return 0;
}
