The Next Permutation#1987
Sign in

The Next Permutation

1 second
32 megabytes
Very easy

A string of decimal digits is given. Print the permutation of these decimal digits such that its value is the immediate next number after the input number. For example:

123 \rightarrow 132
279134399742 \rightarrow 279134423799

It is possible that some permutation has no larger value. For example, .

Input

The first line contains the number of input test cases (1 \leq p \leq 1000). Each of the next lines represents a separate test case and contains its number and a corresponding set of at most decimal digits.

Output

For each test case, print one line. If there is no larger permutation for the input digits, print the data set number followed by a single space and the string BIGGEST. If the solution exists, print the test case number, a single space, and the next permutation of the input digits.

Examples

Example 1

Loading
Loading