#include<cstdio>
#include<cstring>

const int nm=1050;
int d[nm][nm],a[105];
char s1[nm],s2[nm];

int max(int a,int b)
{
    if(a>b)
        return a;
    return b;
}
int main()
{
    //freopen("lp.in","r",stdin);
    int k,i,n,t,j;
    scanf("%d",&t);
    getchar();
    for(k=0;k<t;k++)
    {
        gets(s1+1);
        n=strlen(s1+1);
        for(i=1;i<=n;i++)
        {
            s2[n-i+1]=s1[i];
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(s1[i]==s2[j])
                    d[i][j]=d[i-1][j-1]+1;
                else
                    d[i][j]=max(d[i][j-1],d[i-1][j]);
            }
        }
        a[k]=d[n][n];
    }
    for(i=0;i<t;i++)
    {
        printf("%d" ,a[i]);
        printf("\n");
    }
}