분수

정신병동에 처음 들어온 며칠 동안 베를라가는 인도 총독인 척했다. 곰곰이 생각해 보니 그것은 위험한 짓이었다. 코끼리에 태워 거리를 돌아다니게 할 수도 있으니까. 그는 이야기를 바꾸기로 했다. 다음에 어떤 인물이 될지는 아직 정하지 않았다. 그동안 그는 가장 좋아하는 오락인 솔리테어를 즐기고 있다.

이따금 그는 궁금해진다. 자신이 둔 게임 중 몇 할을 이기는 걸까? 솔리테어 프로그램은 소수점 이하 두 자리까지만 답을 알려 주는데, 베를라가는 정밀한 것을 좋아해서 때때로 비율을 직접 계산한다. 그 답은 비율 자체와 사용하는 진법에 따라 유한소수가 될 수도 있고 순환소수가 될 수도 있다. 그렇다. 미친 회계사들은 십진법뿐 아니라 어떤 위치 기수법이든 쓸 수 있다. 예를 들어 십진법에서 $1/3$은 무한순환소수이고 $4/10$은 유한소수지만, 삼진법에서는 모든 것이 반대다. $1/3$은 유한소수 "$0.1$"이고 $4/10$은 무한순환소수 "$0.101210121012\ldots$"이다.

물론 모든 회계사가 그렇듯 그는 무한소수를 좋아하지 않아서, 승률이 유한소수가 된다고 확신할 때만 승률을 계산한다. 그러려면 게임을 몇 판 더 해야 한다.

베를라가가 추가로 해야 하는 게임의 최소 횟수를 구하도록 도와주자. 전체 게임 횟수는 $M$을 넘으면 안 된다.

입력 파일의 첫 줄에는 세 수가 주어진다. $B$는 기수법의 밑, $M$은 허용되는 최대 게임 횟수, $N$은 질의의 개수이다 ($2 \le B \le 5 \cdot 10^6$, $1 \le M \le 10^{18}$, $1 \le N \le 10^5$).

다음 $N$개의 줄에 질의가 주어진다. 각 줄에는 정수 $a_i$ 하나가 있다. $a_i$는 베를라가가 지금까지 둔 게임의 수이다 ($1 \le a_i \le M$).

출력 파일에는 $N$개의 줄이 있어야 하며, 각 줄에 해당 질의의 답을 출력한다. 각 답은 정수 $A$여야 한다. $A$는 승률이 유한소수가 되도록 하기 위해 추가로 해야 하는 게임의 수이다 ($A \ge 0$). 이때 전체 게임 횟수가 $M$보다 크면 답으로 $-1$을 출력한다.