HS12STSQ - Strange Sequence
Given integers: r (1<r<100) and s we define a sequence X(r,s) in such a way that X(r,s)0 = s and X(r,s)i+1 is equal to X(r,s)i plus the sum of digits of X(r,s)i when expressed in the standard base-r positional system.
Task: given r, s < M < 100000 find out how many elements of X(r,s) are required to reach M, that is, find the smallest i such that X(r,s)i is precisely equal to M.
In the first line you are given three decimal integers: r, M, n, where n<100000 is the number of test cases. In each of the following n lines you are given one decimal, nonnegative integer s specific for a given test case.
For each of the test cases output in the separate line the one requested number in decimal format or -1 if such a number does not exist.
Input: 2 10 3 7 3 8 Output: 1 3 -1 Explanation: 7(Dec) = 111(Bin) The sum of digits of 111(Bin) is 3(Dec) 7+3=10 (Dec) 10 has been reached in one step. 3(Dec) = 11(Bin) The successive elements are (Dec): 5, 7, 10 (3 steps) 8(Dec) = 1000(Bin) The successive elements are (Dec): 9, 11, ... 10(Dec) will not be reached.
Input: 21 1234 3 3 8 1207 Output: -1 -1 1
By solving this problem you score 10 points.