#include <bits/stdc++.h>
using namespace std;

int main() {
	int tt;
	cin>>tt;
	while(tt--)
	{
	    string s;
	    cin>>s;
	    int n=s.size();
	    bool dp[n][n];

        memset(dp,0,sizeof(dp));	    
	    int qq=1;
	    for(int i=0;i<n;i++)dp[i][i]=1;
	    for(int i=0;i<n;i++)
	    {
	        for(int j=0;j<=i;j++)
	        {
	            if(i==j)continue;
	            int row=j;
	            int col=i;
	            if(i==j)dp[i][j]=1;
	            else if((row+1)!=col){
	                if((dp[row+1][col-1]==1) && (s[row]==s[col]))dp[row][col]=1;
	                else dp[row][col]=0;
	            }
	            else 
	            {
	                if(s[row]==s[col])dp[row][col]=1;
	                else dp[row][col]=0;
	            }

	        }
	    }
	    
	    int a=0;
	    int b=0;
	    for(int i=n-1;i>=0;i--)
	    {
	        int flag=0;
	        int r=i;
	        for(int j=0;j<(n-i);j++)
	        {
	            if(dp[j][r]==true){a=j;b=r;flag=1;break;}
	            r++;
	        }
	        if(flag==1)break;
	    }

	    for(int i=a;i<=b;i++)cout<<s[i];
	    cout<<endl;
	    
	}
	return 0;
}