class Solution {
static int t[][];
public static String longestPalindrome(String s11) {
String s22="";
for(int i=0;i<s11.length();i++)
{
s22=s11.charAt(i)+s22;
}
char s1[]=s11.toCharArray();
char s2[]=s22.toCharArray();
lcs(s1,s2,s1.length,s2.length);
return Print_lcs(s1,s2,s1.length,s2.length);
}
static String Print_lcs(char s1[],char s2[],int m,int n)
{
String str="";
int i=m;int k=n;
while(i!=0 && k!=0) {
if(s1[i-1]==s2[k-1])
{
str=s1[i-1]+str;
i--;
k--;
}
else
{
if(t[i-1][k]>t[i][k-1])
i--;
else
k--;
}
}
return str;
}
static void lcs(char s1[],char s2[],int m,int n)
{
t=new int[m+1][n+1];
int res=0;
//base case
for(int i=0;i<m+1;i++)
{
for(int k=0;k<n+1;k++)
{
if(i==0||k==0)
t[i][k]=0;
}
}
for(int i=1;i<m+1;i++)
{
for(int j=1;j<n+1;j++)
{
if(s1[i-1]==s2[j-1]){
t[i][j]=1+t[i-1][j-1];
}
else
t[i][j]=Math.max(t[i][j-1],t[i-1][j]);
}
}
}
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int te=in.nextInt();
in.nextLine();
for(int i=0;i<te;i++)
{
String s11=in.nextLine();
System.out.println(longestPalindrome(s11));
}
}
}