Read problem statements in [Mandarin], [Bengali], [Russian], and [Vietnamese] as well.

One day, Chef's friend gave him a wrong number $W$ containing $N + 1$ digits and said that the actual number $A$ is the largest possible number that can be obtained from deleting exactly one digit of $W$. Chef was able to find $A$ but forgot $W$.

Given $A$, find the smallest possible number $W$ of length $N + 1$ without leading $0$'s that is consistent with the story above. We can show that there is always at least one such $W$ consistent with the story.

------ Input ------

The first line contains an integer $T$, the number of test cases. Then the test cases follow.
Each test case contains a single line of input, an integer $A$.

------ Output ------
For each testcase, output in a single line string representing the answer to the problem.

------ Constraints ------
$1 ≤ T ≤ 100$
$0 ≤ A_{i} ≤ 9$ for all valid $i$, where $A_{i}$ denotes the $i$-th digit of $A$
$A_{1} \neq 0$ (no leading zero)
$10 ≤ |A| ≤ 5000$, where $|A|$ denotes the number of digits of $A$

------ Subtasks ------
Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------
2
9876543211
12345678999
----- Sample Output 1 ------
19876543211
102345678999
----- explanation 1 ------
It can be proven that the above output strings are the smallest possible numbers from which you can arrive at the correct number in the input.

见题面

见题面