游戏的目标是使这个数最小。

　　如今你的任务是帮小明写段程序，求出这个最小数。

输入

第一行是一个数T，表示有T组測试数据。

然后以下有T行， 每行是一个仅仅含有0~9的字符串，表示N张叠在一起的卡片。最左边的数字表示最上方的卡片。



[Technical Specification]

T<=1000

1 <= N <= 100

输出

对于每组測试数据，请在一行内输出能得到的最小数。

例子输入

3

565

9876543210

9876105432

例子输出

556

1234567890

1678905432

AC码：

#include<stdio.h>

int main()

{

	char str[105],ch[110],s;

	int T,i,j,left,right;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%s",str);

		s='9';

		for(i=0;str[i]!='\0';i++)

		{

			if((str[i]!='0')&&str[i]<=s)

			{

				s=str[i];

				j=i;

			}

		}

		left=53;

		right=52;

		ch[left]='9';

		for(i=0;str[i]!='\0';i++)

		{

			if(i>=j)

				break;

			if(str[i]<=ch[left])

			{

				left--;

				ch[left]=str[i];

			}

			else

			{

				right++;

				ch[right]=str[i];

			}

		}

		printf("%c",s);

		for(i=left;i<=right;i++)

			printf("%c",ch[i]);

		for(i=j+1;str[i]!='\0';i++)

			printf("%c",str[i]);

		printf("\n");

	}

	return 0;

}