char s[2000003];
int t[2000002];
main(){
  int T;scanf("%d",&T);
  while(T--){
    int l,i,j,pos=-1,maxn=0;
    scanf("%s",s+1);l=strlen(s+1);
    s[l+1]=1;
    for(i=l+2,j=l;j;++i,--j)
      s[i]=s[j];
    l=i;
    t[1]=0;
    for(i=2,j=0;i<=l;++i){
      while(j&&s[i]!=s[j+1])j=t[j];
      if(s[i]==s[j+1])++j;
      t[i]=j;
    }
    for(i=l;i>=l>>1;--i)
      t[i]>maxn&&(maxn=t[i],pos=i);
    for(i=pos;i>pos-maxn;--i)
      putchar(s[i]);
    puts("");
  }
}