K. ruskal's Reconstruction Number
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a positive integer $$$n$$$, you can choose two adjacent digits of this number and swap them. You can perform this operation at most once (or not at all).

Your task is to find the maximum value of the number after the operation (or without any operation).

Input

The input consists of multiple test cases.

First, there is a line containing an integer $$$T(1 \le T \le 10^5)$$$, indicating the number of test cases.

For each test case, input a positive integer $$$n(1\le n \lt 10^{200000})$$$.

It is guaranteed that for all data in a test case, the sum of the number of digits of $$$n$$$ does not exceed $$$2\times 10^5$$$.

Output

Output a total of $$$T$$$ lines.

For each test case, output an integer representing the maximum value of the given number after at most one operation.

Example
Input
3
9
14623
998544332
Output
9
41623
998544332
Note

In the second test case, you can swap the 1st digit with the 2nd digit.

In the first and third test cases, no operation is needed.