Suppose we think of any 4-digit number - for example, 3633. We then rearrange
the digits to create the largest and smallest numbers possible, then compute
their difference to yield a new number. So in our example, from the digits
3 6 3 3 the largest number we can create is 6333 and the smallest is
3336, and the difference of these two numbers is 2997. Applying these
operations repeatedly, we obtain the sequence
3336 -> 2997 -> 7173 -> 6354 -> 3087 -> 8352 -> 6174
And then because 7641 - 1467 = 6174, every subsequent term in the sequence
is 6174. It turns out that no matter which 4-digit number is initially
chosen, the resulting sequence will (almost) always end in 6174, which is
now known as Kaprekar's Constant after the discovery was made by Indian
mathematician Dattatreya Ramchandra Kaprekar.
The 9 exceptions to this being when all four digits are identical, for
example 5555 -> 0000.
We can see that for the starting value of 3336, we generated a sequence of 7
unique values before seeing the value 6174 repeat. This value that produces itself
when subjected to the algorithm is called a "fixed point". The sequence will always produce the fixed point 6174
when using 4-digit numbers in Base-10, but what if we apply the same rules
to numbers with n digits in Base-b? By changing the base and length of the number,
it now becomes possible for the sequence to have multiple fixed points, or chains of
repeating numbers, depending on the initial value chosen.
Note that if the result of applying the above algorithm to an n-digit number yields a
result less than n, then include the leading zeroes during the next iteration of the algorithm.
For example in Base-10, 3222 -> 0999 -> 8991 -> 8082 -> 6714
Given a number n represented in base b, apply the above Kaprekar's Routine
to the number to generate a sequence of unique values until a repeated value is
encountered, then return the quantity of unique values in the sequence and the
first repeated term.
Input Data
First line is Q, the quantity of testcases.
Q lines then follow, each holding a testcase in the format n b.
Answer
Should consist of Q pairs of space-separated values u r, with ucorresponding
to the quantity of unique terms in the sequence generated by the testcase, and
r corresponding to the first repeated term.
Example
input data:
3
1234 10
abcde 16
zyxwvu 36
answer:
4 6174 8 c5f94 118 qfvka