421. 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 this option. Note that he can only use this option once.

Input Format

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

Output Format

Print the ticket number with the highest win probability for each test case 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