#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define int long long
#define pii pair<int, int>
#define ms(x) memset((x), -1, sizeof (x))
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
const int MAX = (int) 1e6 + 5;
const int MOD = (int) 1e9 + 7;
const int BASE = 347;
int T;
int total;
string S[MAX], s;
bool maximize(int &x, const int &y){
if (x < y){
x = y;
return 1;
}
return 0;
}
namespace sub2{
bool check(){
return (int)s.size() <= 300 && total <= 1800;
}
void solve(){
int n = s.size();
int f[n + 5][n + 5];
memset(f, 0, sizeof f);
s = " " + s;
for (int i = 1; i <= n / 2; i++){
for (int len = 1; len <= n / 2; len++){
if (i + len - 1 < n - i + 1 - len + 1){
bool ok = 1;
for (int j = i; j <= i + len - 1; j++){
ok &= (s[j] == s[n - i + 1 - len + 1 + (j - i)]);
}
if (ok) f[i][len] = 1;
}
else break;
}
}
int dp[n + 5];
memset(dp, 0, sizeof dp);
for (int i = 1; i <= n / 2; i++){
for (int len = 1; len <= n / 2; len++){
if (f[i][len]) maximize(dp[i + len], dp[i] + 1);
}
}
int res = 1;
for (int i = 1; i <= n; i++){
if (dp[res] < dp[i]) res = i;
}
int answer = dp[res] << 1;
if (n & 1 || res < n / 2) answer++;
cout << answer << "\n";
}
}
namespace sub3{
bool check(){
return (int)s.size() <= 5000 && total <= 30000;
}
void solve(){
int n = s.size();
s = " " + s;
int Pw[n + 5], H[n + 5];
Pw[0] = 1, H[0] = 1;
for (int i = 1; i <= n; i++) Pw[i] = Pw[i - 1] * BASE % MOD;
for (int i = 1; i <= n; i++) H[i] = (H[i - 1] * BASE + (s[i] - 'a' + 1)) % MOD;
auto ask = [&](const int &l, const int &r) -> int{
return (H[r] - H[l - 1] * Pw[r - l + 1] % MOD + MOD) % MOD;
};
int f[n + 5][n + 5];
memset(f, 0, sizeof f);
for (int i = 1; i <= n / 2; i++){
for (int len = 1; len <= n / 2; len++){
if (i + len - 1 < n - i + 1 - len + 1){
bool ok = ask(i, i + len - 1) == ask(n - i + 1 - len + 1, n - i + 1);
if (ok) f[i][len] = 1;
}
else break;
}
}
int dp[n + 5];
memset(dp, 0, sizeof dp);
for (int i = 1; i <= n / 2; i++){
for (int len = 1; len <= n / 2; len++){
if (f[i][len]) maximize(dp[i + len], dp[i] + 1);
}
}
int res = 1;
for (int i = 1; i <= n; i++){
if (dp[res] < dp[i]) res = i;
}
int answer = dp[res] << 1;
if (n & 1 || res < n / 2) answer++;
cout << answer << "\n";
}
}
namespace greedy{
bool check(){
return 1;
}
void solve(){
int n = s.size();
s = " " + s;
int Pw[n + 5], H[n + 5];
Pw[0] = 1, H[0] = 1;
for (int i = 1; i <= n; i++) Pw[i] = Pw[i - 1] * BASE % MOD;
for (int i = 1; i <= n; i++) H[i] = (H[i - 1] * BASE + (s[i] - 'a' + 1)) % MOD;
auto ask = [&](const int &l, const int &r) -> int{
return (H[r] - H[l - 1] * Pw[r - l + 1] % MOD + MOD) % MOD;
};
int answer = 0, prev = 1;
for (int i = 1; i <= n / 2; i++){
int len = i - prev + 1;
if (ask(prev, i) == ask(n - prev + 1 - len + 1, n - prev + 1)){
answer++;
prev = i + 1;
}
}
answer <<= 1;
if (prev != n / 2 + 1 || n & 1) answer++;
cout << answer << "\n";
}
}
signed main(){
#define name "sixcup"
if (fopen(name".inp", "r")){
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
for (int i = 1; i <= T; i++){
cin >> S[i];
total += S[i].size();
}
for (int i = 1; i <= T; i++){
s = S[i];
// if (sub2::check()) {sub2::solve(); continue;}
// if (sub3::check()) {sub3::solve(); continue;}
if (greedy::check()) {greedy::solve(); continue;}
}
return 0;
}
