High School Programming League Problems Archive

Given integers: r (1<r<100) and s we define a sequence X(r,s) in such a way that X(r,s)₀ = 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.

Input

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.

Output

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.

Example 1

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.

Example 2

Input:
21 1234 3
3
8
1207

Output:
-1
-1
1

Scoring

By solving this problem you score 10 points.