In the previous problem we observed how we can take some n-digit number in base b, and create a
sequence of unique integers using the algorithm known as Kaprekar's Routine. By rearranging the digits to obtain the largest difference,
we created the following sequence, terminating in Kaprekar's Constant.
3336 -> 2997 -> 7173 -> 6354 -> 3087 -> 8352 -> 6174
Let's choose some other random numbers - 7489 and 1797 - and create some sequences from those as well.
1797 -> 7992 -> 7173 -> 6354 -> 3087 -> 8352 -> 6174
7489 -> 5085 -> 7992 -> 7173 -> 6354 -> 3087 -> 8352 -> 6174
There is actually a bit of overlap with these sequences, and so we could start to build a "tree" from them:
1797
\/
7489 -> 5085 -> 7992
\/
3336 -> 2997 -> 7173 -> 6354 -> 3087 -> 8352 -> 6174
We can see here that in the above graph, there are a total of 7 possible sequences which could be created
which contain the value 7173, being the sequences starting with 1797, 7489, 5085, 7992, 3336,
2997, and 7173. Although, there could be several more possible sequences containing 7173 that we
haven't listed here yet...
Given a base b, n, and some n-digit integer x, compute how many unique Kaprekar Sequences exist which contain x.
All values for this problem will be padded with leading zeroes where applicable, and so n can be safely assumed from the
given value of x. For example if x = 0900 then you can safely assume n = 4.
Input Data
First line is Q, the quantity of testcases.
Q testcases will then follow in the format x b.
Answer
Should consists of Q space-separated values corresponding to the total quantity of Kaprekar Sequences which
contain the value x, in each described testcase.
Example
input data:
3
3201 4
df2 16
7173 10
answer:
7 517 1345