Next Greater Number Problem Statement

Given a string S which represents a number, determine the smallest number strictly greater than the original number composed of the same digits. Each digit's frequency from 0-9 must match the original.

Input:

The first line is an integer T, the number of test cases.
Each test case contains one line with the string S.

Output:

For each test case, output the smallest number strictly greater using the same set of digits or -1 if it doesn't exist.

Example:

If given S = '56789', the output should be 56798. Note that 56790 is also greater but uses different digits.

Constraints:

• 1 ≤ T ≤ 100
• 1 ≤ len(S) ≤ 104
• The function has a time limit of 1 second.

Note:

The input string is non-empty with no leading zeros. Implement the function; printing is handled elsewhere.