#include <bits/stdc++.h>
using namespace std;
#define int long long
#define bit(x, i) ((x >> i) & 1)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
const int maxn = (int)1e6 + 7, mod = (int)1e6 + 7, base = 103, m2 = mod * mod;
template <class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
} return false;
}
int numtest, sum_test = 0, max_test;
vector <string> str;
namespace subtask1 {
int calc (string s, int n) {
int res = 0;
vector <string> ans;
FOR(mask, 0, (1 << n) - 1) {
int cnt = 0; string tmp[30];
string t = ""; t += s[0];
FOR(i, 1, n - 1) {
if (bit(mask, i) == bit(mask, i - 1)) t += s[i];
else {
tmp[++cnt] = t;
t = ""; t += s[i];
}
}
tmp[++cnt] = t;
int k = cnt, ok = 1;
FOR(i, 1, k) {
if (tmp[i] != tmp[k - i + 1]) {ok = 0; break;}
}
if (ok == 1) {
if (res < cnt) {
res = cnt;
ans.clear();
FOR(i, 1, cnt) ans.push_back(tmp[i]);
}
}
}
return res;
}
void process() {
FOR(test, 1, numtest) {
string s = str[test - 1];
int n = s.size();
cout << calc(s, n) << '\n';
}
}
};
namespace subtask2 {
int pref[350], p[305];
int get_hash (int l, int r) {
return (pref[r] - pref[l - 1] * p[r - l + 1] + m2) % mod;
}
int calc (int n, string s) {
vector <vector <int>> dp(n + 100, vector <int> (n + 100, 0));
memset(pref, 0, sizeof(pref));
memset(p, 0, sizeof(p)); p[0] = 1;
FOR(i, 1, n) {
pref[i] = (pref[i - 1] * base + (s[i] - 'a')) % mod;
p[i] = (p[i - 1] * base) % mod;
}
FORD(l, n, 1) {
dp[l][l] = 1;
FOR(r, l + 1, n) {
FOR(x, 1, (r - l + 1)) {
int tmp_1 = get_hash(l, l + x - 1);
int tmp_2 = get_hash(r - x + 1, r);
if (tmp_1 == tmp_2) {
if (l + x - 1 < r - x + 1) maximize(dp[l][r], dp[l + x][r - x] + 2);
else if (l + x - 1ll == r && r - x + 1ll == l) dp[l][r] = max(dp[l][r], 1ll);
}
}
}
}
return dp[1][n];
}
void process() {
FOR(test, 1, numtest) {
string s = str[test - 1];
int n = s.size();
s = '&' + s;
cout << calc(n, s) << '\n';
}
}
};
namespace subtask3 {
int pref[5005], p[5005];
int get_hash(int l, int r) {
return (pref[r] - pref[l - 1] * p[r - l + 1] + m2) % mod;
}
int calc (int n, string s) {
memset(pref, 0, sizeof(pref));
memset(p, 0, sizeof(p));
vector <int> dp(n + 1, 0);
p[0] = 1;
FOR(i, 1, n) {
pref[i] = (pref[i - 1] * base + (s[i] - 'a')) % mod;
p[i] = (p[i - 1] * base) % mod;
}
FOR(i, 1, n / 2) {
FORD(j, i, 1) {
int sz = i - j + 1;
if (get_hash(j, i) == get_hash(n - i + 1, n - i + 1 + sz - 1)) {
if (j - 1 == 0) dp[i] = max(dp[i], dp[j - 1] + 2);
else if (dp[j - 1] != 0) dp[i] = max(dp[i], dp[j - 1] + 2);
}
}
}
int ans = 0;
if (n & 1) FOR(i, 0, n / 2) ans = max(ans, dp[i] + 1);
else {
FOR(i, 0, n / 2 - 1) ans = max(ans, dp[i] + 1);
ans = max(ans, dp[n / 2]);
}
return ans;
}
void process() {
FOR(test, 1, numtest) {
string s = str[test - 1]; int n = s.size();
s = '&' + s;
cout << calc(n, s) << '\n';
}
}
};
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
//freopen("sixcup.inp", "r", stdin);
//freopen("sixcup.out", "w", stdout);
cin >> numtest;
FOR(test, 1, numtest) {
string s; cin >> s;
str.push_back(s);
sum_test += s.size();
maximize(max_test, s.size());
}
//if (max_test <= 20 && sum_test <= 120) return subtask1::process(), 0;
//if (max_test <= 300 && sum_test <= 1800) return subtask2::process(), 0;
return subtask3::process(), 0;
}
