11151

#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>

using namespace std;

int table[1001][1001];

int main()
{
	int n,len;
	string s;

	cin>>n;
	getchar();

	while(n--)
	{
		getline(cin,s);

		if(s=="")
		{
			cout<<0<<"\n";
			continue;
		}

		memset(table,0,sizeof(table));
		len = s.size();
		for(int i=0;i<=len;i++)
		{
			table[i][i]=1;
		}

		for(int length=2;length<=len;length++)
		{
			for(int i=0;i<=len-length+1;i++)
			{
				int end=i+length-1;
				if(end<0 || end>=len)
				continue;
				if(s[i]==s[end] && length==2)
				{
					table[i][end]=2;
				}
				else if(s[i]==s[end])
				{
					table[i][end]=table[i+1][end-1]+2;
				}
				else
				{
					table[i][end] = max(table[i+1][end],table[i][end-1]);
				}
			}
		}

		cout<<table[0][len-1]<<"\n";
	}

	return 0;
}