#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; }