最近，Nvoenewr 在课堂上学习了回文数。

回文数是一个非负整数，从左向右读和从右向左读都是一样的。例如，0, 1, 2, 11, 99, 232, 666, 998244353353442899 是回文数，而 10, 23, 233, 1314 不是回文数。

现在，给定一个数字，Nvoenewr 可以利用他在课堂上学到的循环来判断它是否为回文数。但他现在对另一个问题产生了兴趣：第 $K$ 个回文数是什么？这个问题对他来说似乎太难了，所以他现在向你寻求帮助。

Nvoenewr 从小到大计数，如下所示：0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101 等等。因此，第一个回文数是 0，第十一个回文数是 11。

Nvoenewr 可能会问你几个问题，且 $K$ 可能非常大。

输入格式

第一行包含一个整数 $T$ ($T \le 20$)，表示 Nvoenewr 将要询问的问题数量。

接下来的 $T$ 行，每行包含一个整数 $K$。你需要为 Nvoenewr 找到第 $K$ 个回文数。

假设 $K$ 是一个 $n$ 位数。保证 $K \ge 1$，$1 \le n \le 100000$，且所有 $T$ 个问题中 $n$ 的总和不超过 $1000000$。

输出格式

输出 $T$ 行。第 $i$ 行包含你对 Nvoenewr 第 $i$ 个问题的回答。

样例

输入 1

4
1
10
11
20

输出 1

0
9
11
101