814. The Sunday Lottery

0

Medium

Vivek has purchased a Lottery Ticket from The Sunday Lottery. Each ticket has a unique number engraved on it. Vivek has received a tip that the higher the ticket number, the greater the chances of winning. The Sunday Lottery allows customers to swap any two digits of their ticket number once. Given a ticket number, Vivek wants to know the ticket number with the highest probability of winning if he uses the swap option. Note that he can only use the swap option once.

Input Format

The first line of input contains an integer T, denoting the number of test cases. The following T lines each contain an integer L, representing a Lottery Number.

Output Format

For each test case, print the ticket number with the highest probability of winning on a new line.

Example

Input

2
3845
7731

Output

8345
7731

Constraints

1 <= T <= 10^4
1 <= L <= 10^8

Loading...

View Submissions

Console