Rise and Fall

A number is said to Rise and Fall if the decimal representation can be broken up into two parts (possibly empty) where the first part has digits in nondecreasing order and the second part has digits in nonincreasing order. Note that a proper integer may not have any leading $0$s.

Compute the largest number less than or equal to an input number that rises and falls.

Input

The first line of input contains an integer $t$ ($1 \le t \le 10^5$), which is the number of test cases.

Each of the next $t$ lines contains a single integer $n$ ($1 \le n < 10^{100{,}000}$). Each is a single test case.

  • Note: that is not a typo. The integer can be up to $10^5$ digits long.

The sum of the lengths of all input test cases will not exceed $10^5$.

Output

For each test case, output a single line with a single integer, which is the largest number less than or equal to the $n$ for that test case that rises and falls.

Sample Input 1 Sample Output 1
2
29041
56577
29000
56555