Background

After watching the intro of this MV, you should know what the heck $f$ is (just kidding).

Problem Description

Define $f(x)$ as the number formed by reversing the digits of $x$.

For example:

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

Given an integer $n$, find the largest $k$ such that for every positive integer $m$ in the interval $[1,k]$, we have $f(m)\leq n$.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

Each of the next $T$ lines contains a positive integer $n$.

Output Format

Output $T$ lines, one for each test case, containing the answer.

3
12
991
114514

11
298
100001

2
99999
99998

100000
99998

Hint

For sample test $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$. Therefore, the maximum $k$ is $11$.

This problem uses bundled testdata.

• $\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)}:$ No special constraints.

For $100\%$ of the data, $1\leq T\leq10^5,1\leq n\leq10^{18}$.

Hint: unsigned long long can store natural numbers from $0$ to $18,446,744,073,709,551,615(2^{64}-1)$.

Translated by ChatGPT 5