Kaprekar Routine and Kaprekar Circle

Kaprekar, a mathematician, discovered an interesting property of numbers. Consider a K-digit number (with at least two different digits). Perform the following procedure:

1. Rearrange its digits to form the largest possible number and the smallest possible number (if necessary, use leading zeros so that the result has exactly K digits).
2. Subtract the smaller number from the larger one.
3. Repeat the process with the result.

For 4-digit numbers, this process always converges to the fixed number \(6174\) (known as Kaprekar's constant). For other values of \(K\), the process eventually falls into a repeating cycle (called the Kaprekar circle). For example, starting with the 5-digit number 54321:

[ 54321 - 12345 = 41976, ] [ 97641 - 14679 = 82962, ] [ 98622 - 22689 = 75933, ] [ 97533 - 33579 = 63954, ] [ 96543 - 34569 = 61974, ] [ 97641 - 14679 = 82962, ]

The cycle (Kaprekar circle) here is: 82962, 75933, 63954, 61974.

Your task is to simulate the Kaprekar process for a given K-digit number until a number appears for the second time. Then, output the distinct numbers forming the cycle, in the order they appear (starting from the first occurrence of the repeated number).

inputFormat

The input begins with an integer \(T\) (\(T \ge 3\)), representing the number of test cases. Each of the following \(T\) lines contains a single K-digit number (as a string) where not all digits are identical. Note that if the result of any subtraction has fewer than \(K\) digits, leading zeros must be added to maintain \(K\) digits.

outputFormat

For each test case, output the numbers in the Kaprekar cycle (i.e. the repeating part) separated by a single space on a new line. If the process converges (as in the 4-digit case where the cycle is just \(6174\)), output that number.

sample

3
4321
54321
2111

6174
82962 75933 63954 61974
6174