1. 

/**
* ACM 11151 Longeste Palindrome
* UVa Status: accepted
* Run Time: 0.280
* Category: Dynamic Programming
* @author Evgeni Pavlidis evgenipavlidis@yahoo.de
*/


#include <iostream>

using namespace std;

#define MAX_SIZE 1000
#define MAX(a,b) ( (a > b)? (a) : (b) )

static int m[MAX_SIZE+1][MAX_SIZE+1];

// longest common subsequence
int lcs(string a, string b)
{
int l = a.length();

for(int i=0; i < l; i++)
m[i][0] = 0;
for(int j=0; j < l; j++)
m[0][j] = 0;

for(int i=1; i <= l; i++)
for(int j=1; j <= l; j++)
if(a[i-1] == b[j-1])
m[i][j] = m[i-1][j-1] + 1;
else
m[i][j] = MAX(m[i][j-1], m[i-1][j]);

return m[l][l];
}

string reverse(string s)
{
string r = "";
for(int i = s.length() -1; i >= 0; i--)
r += s[i];
return r;
}

int main()
{
int cases;
cin >> cases;
string s;
cin.ignore(1,'\n');

for(int c=0; c < cases; c++)
{
getline(cin,s);
cout << lcs(s,reverse(s)) << endl;
}

return 0;
}