Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

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.

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.


Added by:kuszi
Date:2012-10-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC GAWK MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV ICK JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET
Resource:High School Programming League

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.