Find the Next Greater Number with the Same Set of Digits

Given a string S that represents a number, determine the smallest number that is strictly greater than the original number and has the same set of digits. The frequency of each digit from 0 to 9 should remain unchanged.

Example:

Input:

S = "56789"

Output:

56798

Explanation:

Although 56790 is greater than 56789, it includes a '0' which is not in the original number and misses the digit '8'.

Constraints:

• 1 ≤ T ≤ 100
• 1 ≤ len(S) ≤ 104
• The number S has no leading zeros.

Input:

The first line contains an integer T, the number of test cases.
The following T lines each contain a string S representing a number.

Output:

For each test case, output the smallest number greater than S with the same set of digits.

Note:

If no such number exists, return -1. Implementation of function is required, printing is handled elsewhere.