Kaprekar's Routine for d-digit Numbers

In 1955, mathematician D. R. Kaprekar discovered an interesting property for 4-digit numbers. For any 4-digit number (with digits not all identical), if you arrange its digits in descending order to form a number \(A\) and in ascending order (preserving leading zeros) to form a number \(B\), then \(A - B\) yields a new 4-digit number. Repeating this process eventually leads to a fixed cycle; for the 4-digit case the cycle is just the number \(6174\) (called the "black hole number").

This phenomenon can be generalized to any \(d\)-digit number (with not all digits identical). It can lead to a cycle involving one or more numbers. Given a \(d\)-digit number, perform the following steps:

1. Arrange its digits in descending order to get \(A\) and in ascending order (with leading zeros) to get \(B\).
2. Compute \(A - B\) and produce a new \(d\)-digit number (pad with leading zeros if necessary).
3. Repeat the above process until a number repeats. The first number that repeats (i.e. the entry point of the cycle) is the answer.

For example, starting with 50985:

50985  --->  98550 - 05589 = 92961
92961  --->  99621 - 12699 = 86922
86922  --->  98862 - 26889 = 71973
71973  --->  97731 - 13779 = 83952
83952  --->  98532 - 23589 = 74943
74943  --->  97443 - 34479 = 62964
62964  --->  96642 - 24669 = 71973

Here, 71973 is encountered again, so the output should be 71973.

inputFormat

The first line contains an integer \(n\) (the number of test cases). Each of the following \(n\) lines contains a \(d\)-digit number (with not all digits identical). Note that the number may contain leading zeros, and \(d\) is determined by the length of the number provided.

outputFormat

For each test case, output the first number that repeats (i.e. the entry point of the cycle) on a separate line.

sample

3
2024
1234
50985

6174
6174
71973