Submit | All submissions | Best solutions | Back to list |

## 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 8Output:1 3 -1Explanation: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 1207Output:-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 |