题目描述

在LCD上显示数字很有趣，有些数字可以倒着看，有些数字则不行。例如：6可以倒看成9，而0,1,2,5,8倒过来看还是0,1,2,5,8。把所有能倒着看的整数，从0开始，按照由小到大排列后，求第n个数，并以倒着的形式输出。如果有前导的0，一定要输出。

输入

第一行为正整数t(≤1000)，表示数据组数；接下来t行，每行一个正整数n(≤10的9次方）

输出

对于每个整数n，输出第n个可以倒着看的整数。

样例1

输入

2
8
1000

输出

11
6262

不要代码，只需要思路。