#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define debug(x) cout << #x << " = " << (x) << endl;
#define fi first
#define se second
#define left __left
#define right __right
#define prev __prev
#define next __next
template <class X, class Y>
bool maximize(X &x, Y y) {
if (x < y) return x = y, true;
else return false;
}
template <class X, class Y>
bool minimize(X &x, Y y) {
if (x > y) return x = y, true;
else return false;
}
const int MOD[] = {(int) 1e9 + 2277, (int) 1e9 + 5277};
const int base = 256;
const int NMOD = 1;
struct Hash {
int value[NMOD];
Hash() {
memset(value, 0, sizeof(value));
}
bool operator == (const Hash &other) const {
REP(i, NMOD) if (value[i] != other.value[i]) return false;
return true;
}
bool operator != (const Hash &other) const {
REP(i, NMOD) if (value[i] != other.value[i]) return true;
return false;
}
bool operator < (const Hash &other) const {
REP(i, NMOD) if (value[i] != other.value[i]) return value[i] < other.value[i];
return false;
}
};
#define MAX_N 1'000'100
string s;
int lenS;
int pw[NMOD][MAX_N + 2], hs[NMOD][MAX_N + 2];
int dp[MAX_N + 2];
void buildHash() {
REP(j, NMOD) {
pw[j][0] = 1, hs[j][0] = 0;
FOR(i, 1, MAX_N) pw[j][i] = 1LL * pw[j][i - 1] * base % MOD[j];
FOR(i, 1, lenS) hs[j][i] = (hs[j][i - 1] + 1LL * pw[j][i - 1] * s[i]) % MOD[j];
}
}
Hash getHash(int l, int r) {
assert(l <= r);
Hash res;
REP(i, NMOD) {
int tmp = hs[i][r] - hs[i][l - 1];
if (tmp < 0) tmp += MOD[i];
res.value[i] = 1LL * tmp * pw[i][MAX_N - l + 1] % MOD[i];
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(nullptr);
#define task "test"
if (fopen(task".inp","r")) {
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
int t;
cin >> t;
while (t--) {
cin >> s;
lenS = SZ(s);
s = '*' + s;
buildHash();
memset(dp, -1, (lenS + 2) * sizeof(int));
dp[0] = 0;
FOR(i, 1, lenS >> 1) {
FOR(j, 1, i) if (dp[j - 1] != -1 && getHash(j, i) == getHash(lenS - i + 1, lenS - j + 1)) {
maximize(dp[i], dp[j - 1] + 1);
}
}
int ans = 1;
FOR(i, 1, lenS >> 1) {
int tmp = dp[i] * 2;
if (2 * i < lenS) ++tmp;
maximize(ans, tmp);
}
cout << ans << "\n";
}
return 0;
}
