#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[3010];
int len;
int dp[3010][3010];
int solve(int l,int r)
{
if(l>r) return 0;
if(l==r) return 1;
if(s[l]==s[r])
return dp[l][r] = solve(l+1,r-1) + 2;
else
return dp[l][r] = max(solve(l+1,r),solve(l,r-1));
}
int main()
{
int T;
scanf("%d",&T);
getchar();
while(T--)
{
gets(s);
len=strlen(s);
memset(dp,-1,sizeof dp);
printf("%d\n",solve(0,len-1));
}
}