小途最近宅在家里无聊，于是他发明了一种有趣的游戏，游戏道具是N张叠在一起的卡片，每张卡片上都有一个数字，数字的范围是0~9，游戏规则如下：
首先取最上方的卡片放到桌上，然后每次取最上方的卡片，放到桌上已有卡片序列的最右边或最左边。
当N张卡片全部都放到桌上后，所有卡片将构成一个完整的数，这个数不能有前导0，也就是说最左边的卡片上的数字不能是0，游戏的目标是使这个数最小。
现在你的任务是帮小途写段程序，找出这个最小的数。
第一行是一个数T, 表示有T组测试数据；
然后下面有T行，每行是一个只含有0~9的字符串，表示N张叠在一起的卡片，最左边的数字表示最上方的卡片。
对于每组测试数据，请在一行内输出能得到的最小数。
3 565 9876543210 9876105432
556 1234567890 1678905432
T<=1000
1<=N<=100