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

using namespace std;

# define input "elimin2.in"
# define output "elimin2.out"

# define max 2003
# define maxp 2001003
long l[maxp],ant[maxp],n,i,j,t,poz,val,ma,rez[max],m;
int v[maxp],d[maxp];

char s[max];

int main()
{
	freopen(input,"r",stdin);
	freopen(output,"w",stdout);

	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",&s);
		n = strlen(s);
		poz =0;
		for(i = 1;i<=n;++i)
		{
			for(j=n;j>=i;--j)
			{
				if(s[i-1] == s[j-1])
				{
					v[++poz] =i;
					d[poz]= j;
				}
			}
		}

		l[1] = 1;

		n=poz;
		for(i=2;i<=n;++i)
		{
			ant[i]=0;
			poz = 0;
			if(s[v[i]] == '0')
				ma=-5;
			else
				ma=1;

			for(j=i-1;j;--j)
			{
				if(v[i] > v[j] && d[i]<d[j] &&ma==l[j]+1)
				{
					if(s[v[j]-1] > s[v[poz]-1])
						poz = j;
				}
				if(v[i] > v[j]&& d[i]<d[j] && ma < l[j]+1)
				{
					ma = l[j]+1;
					poz = j;
				}
			}
			l[i] = ma;
			ant[i] = poz;
		}
		ma = 0;
		for(i=1;i<=n;i++)
		{
			if(l[i] == ma)
				if(s[v[poz]-1] < s[v[i]-1])
					poz = i;
			if(l[i] > ma)
				ma = l[i],poz=i;
		}
		m = 0;
		val = poz;
		while(poz)
		{
			rez[++m] = s[v[poz]-1]-'0';
			poz = ant[poz];
		}
		if(d[val] == v[val])
		{
			for(i = m;i>=2;--i)
				printf("%ld",rez[i]);
			printf("%ld",rez[1]);
			for(i = 2;i<=m;++i)
				printf("%ld",rez[i]);
		}
		else
		{
			for(i = m;i>=1;--i)
				printf("%ld",rez[i]);
			for(i = 1;i<=m;++i)
				printf("%ld",rez[i]);
		}

		printf("\n");
	}


	return 0;
}