Next Permutation

Time limit1sMemory limit128 MB

Summary

Given an integer A, find the smallest permutation of its digits that is strictly greater than A, or print USELESS if none exists.

Level: Medium4 of 10
Topics: Array, String, Greedy, Two pointers
Solved: No attempts yet

Problem

You are given a positive integer $A$ . Among all integers whose digits are a rearrangement (a permutation) of the digits of $A$ , find the smallest one that is strictly greater than $A$ — in other words, the next larger permutation of $A$ ; call it $B$ .

For example, if $A = 2413$ , the next larger permutation is $2431$ .

If $A$ is already the largest number that can be formed from its digits (no larger permutation exists), print USELESS instead.

Input

The first line contains an integer $T$ , the number of test cases. Each of the following $T$ lines contains a single integer $A$ ( $A \le 2{,}000{,}000$ ).

Output

For each test case, print the next larger permutation $B$ of $A$ on its own line. If it does not exist, print USELESS.

Examples5

Example 1

Input

Expected output

251337
1243
USELESS
4344

Example 2
Input
```
3
5
21
111
```
Expected output
```
USELESS
USELESS
USELESS
```
Example 3
Input
```
2
12
1234
```
Expected output
```
21
1243
```
Example 4
Input
```
3
115
151
511
```
Expected output
```
151
511
USELESS
```
Example 5
Input
```
2
2413
2431
```
Expected output
```
2431
3124
```