Problem G
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.

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 ≤ t ≤ 10⁵), which is the number of test cases.

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

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

The sum of the lengths of all input test cases will not exceed 10⁵.

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.

2
29041
56577

29000
56555