题目描述

坤坤又在练习跳跃了。可由于他跳的太大力，把旁边的一些数都给震倒了，例如下面这些可怜的数，坤坤暂且把它叫做 $kk(n)$：

• kk(114)=411
• kk(1919810)=189191

当然坤坤十分的闲，他想知道对于一个数 $n$，满足 $[1,k]$ 中的数 $m$ ( $kk(m) \leq n$ )，请你帮坤坤求出最大的 $k$

输入格式

多组数据。 输入一个 $T$ 和 $T$ 个 $n$。

输出格式

对于每个 $n$，输出满足条件最大的 $k$。

样例 #1

样例输入 #1

4
114
514
1919
810

样例输出 #1

101
105
1001
108

样例 #2

样例输入 #2

3
99
98
10

样例输出 #2

100
98
10

提示

输入数据量较大可以使用__int128，需要快读快写，考察各位的快度快写熟练读。也可以用高精，但我懒得打。 数据范围：

• 对于 20% 的垃坤数据，$T \leq 10^2$，$n \leq 10^4$
• 对于 50% 的送分数据，$T \leq 10^4$，$n \leq 10^{8}$
• 对于 80% 的靠脑子数据，$T \leq 10^5$，$n \leq 10^{15}$

对于 100% 的数据，$T \leq 5\times10^5$，$n \leq 10^{30}$