#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int maxn = 5010;
short dp[maxn];
short mxl[maxn][maxn];
int n;
string s;
inline void fill_mxl()
{
int mid = n/2;
for(int i = mid-1; i >= 0; i--)
{
for(int j = n-1; j >= mid; j--)
{
mxl[i][j-mid] = 0;
if(s[i] == s[j])
{
if(i == mid-1 or j == n-1)
mxl[i][j-mid] = 1;
else
mxl[i][j-mid] = 1+mxl[i+1][j-mid+1];
}
}
}
}
inline void fill_dp()
{
int mid = n/2;
if(n & 1)
dp[mid] = 1;
else
dp[mid] = 0;
for(int i = mid-1; i >= 0; i--)
{
dp[i] = 1;
for(int j = i; j < mid; j++)
{
if(mxl[i][n-1-j-mid] >= j-i+1)
dp[i] = max(dp[i], (short)(dp[j+1]+2) );
}
}
//for(int i = 0; i < mid; i++)
// cerr << dp[i] << " ";
//cerr << endl;
}
inline void solve()
{
cin >> s;
n = s.size();
fill_mxl();
fill_dp();
cout << dp[0] << endl;
}
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T; cin >> T;
while(T--)
{
solve();
}
return 0;
}
