天佑舅舅去年开始当了船长，他和他的船员们已经朝着字节大陆的荒凉海滨进发了数月之久 ，一路上他们喝着七星二锅头，谈论着故事。在这种时候，天佑舅舅常常想起自己的外甥。今天，他讲了一个故事，有关于天佑如何帮他想出了一个有趣的问题，并让其他船员们去解决它。

  一开始，天佑舅舅在木板上写了一个n位正整数x。然后，他擦掉x又写了整数k，k由x各位数字的二进制表达（不包括开头的0）前后连接而成，例如，x=729时，k=111101001（因为7=111，2=10，9=1001）。

  一段时间后，天佑舅舅不知道怎么进一步处理 k来让问题更有趣，于是求助于天佑。天佑想了想决定擦除k的后n位数，将这个新数命名为r。

  最终，天佑提议找到x为n位数时，最大值r所对应的整数x。如果最大值r对应多个x，则取这些x中的最小值。

所有船员包括船长天佑舅舅都迅速做出了这题，除了喝醉的船舱服务员陈大伟，你怎么样？

注意：本题中我们将整数（x或k）当作数字比较（无论天佑舅舅写了什么），所以729<1999,111<1000）

第一行包含一个整数t(1<=t<=1000)——测试数据的数目

下面t行各行包含一个测试数据整数n(1<=n<=10^5)——你需要寻找的整数x的位数n

我们保证所有n的和不超过2*10^5。

对每一个测试数据，输出最小的n位数正整数x，这个x按天佑的方法求出的r是所有可能中最大的。

使用第二个测试数据时（n=3），如果天佑舅舅取x为998，则k=100110011000。天佑通过擦除末尾3位数会得到r=100110011。

显然易证明10110011是r的可能取值的最大值，同时r=1011001时，998是 x的最小值。

宋鑫禹2021