Migrated from Lutece 355 The Next Permutation

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

For this problem, you will write a program that takes a (possibly long) string of decimal digits, and outputs the permutation of those decimal digits that has the next larger value (as a decimal number)

than the input number. For example:

• 123 $\rightarrow$ 132
• 279134399742 $\rightarrow$ 279134423799

It is possible that no permutation of the input digits has a larger value. For example, 987.

Input

The first line of input contains a single integer $P$, ($1\leq P\leq 1000$), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by up to $80$ decimal digits which is the input value.

Output

For each data set there is one line of output. If there is no larger permutation of the input digits, the output should be the data set number followed by a single space, followed by the string BIGGEST. If there is a solution, the output should be the data set number, a single space and the next larger permutation of the input digits.

Samples

3
1 123
2 279134399742
3 987

1 132
2 279134423799
3 BIGGEST

Resources

Greater New York 2009