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

123 → 132

279134399742 → 279134423799

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

Input

The first line contains the number of input test cases p (1 ≤ p ≤ 1000). Each next line represents a separate test and contains its number and a corresponding set of no more than 80 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 input digits.