题目背景

看完这首 mv 的前奏之后你应该知道 $f$ 是什么鬼了（误）。

题目描述

定义 $f(x)$ 是 $x$ 的各位数码翻转以后形成的数。

例如：

• $f(12323)=32321$
• $f(114514)=415411$
• $f(250)=52$

---

给定一个 $n$。求最大的 $k$，使得对于所有处于 $[1,k]$ 区间中的正整数 $m$，有 $f(m)\leq n$。

输入格式

本题多测

第一行一个正整数 $T$ 表示测试点数目。

接下来每个测试点一个正整数 $n$。

输出格式

$T$ 行，对应每个测试点的答案。

3
12
991
114514

11
298
100001

2
99999
99998

100000
99998

提示

对于测试样例 $1$： $f(1)=1,f(2)=2,f(3)=3,f(4)=4,f(5)=5,f(6)=6,f(7)=7,f(8)=8,f(9)=9,f(10)=1,f(11)=11,f(12)=21$。所以 $k$ 最大为 $11$。

---

本题采用捆绑测试

• $\text{subtask1(10pts)}:1\leq T,n\leq10^3$。
• $\text{subtask2(30pts)}:1\leq n\leq10^6$。
• $\text{subtask3(40pts)}:1\leq n\leq10^9$。
• $\text{subtask4(20pts)}:$ 无特殊限制。

对于 $100\%$ 的数据，$1\leq T\leq10^5,1\leq n\leq10^{18}$。

提示：unsigned long long 可以储存 $0$ 到 $18,446,744,073,709,551,615(2^{64}-1)$ 的自然数。