Rise and Fall

Time limit1sMemory limit1024 MB

Summary

Given a huge decimal string, find the largest number no greater than it whose digits split into a nondecreasing prefix and a nonincreasing suffix.

Level: Hard8 of 10
Topics: Greedy, String, Implementation, Math
Solved: No attempts yet

Problem

A number is said to Rise and Fall if its decimal representation can be split into two parts (either of which may be empty) such that 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 \le t \le 10^5$ ), the number of test cases.

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

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

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

Output

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

Examples1

Example 1
Input
```
2
29041
56577
```
Expected output
```
29000
56555
```