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.

Problem hidden

## HS12STSQ - Strange Sequence

no tags

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: ICK Resource: High School Programming League