4891 - 数位动态-魔鬼数

通过次数

1

提交次数

7

Time Limit : 1 秒
Memory Limit : 128 MB

古代人认为666是属于魔鬼的数。 不但如此,只要某数字的十进制表示中有三个连续的6,古代人也认为这是个魔鬼的数,比如666,1666,6663,16666,6660666等等。 古代典籍中经常用“第X小的魔鬼的数”来指代这些数,这给研究人员带来了极大的不便。 现在请编写一个程序,可以实现输入X,输出对应的魔鬼数。

Input

第一行包含整数T,表示共有T组测试数据

Output

每组测试数据占一行,输出一个魔鬼数

Examples

Input

3
2
3
187

Output

1666
2666
66666

Hint

1≤T≤1000, 1≤X≤5∗10^7