在精神病院度过的最初几天里，贝尔拉加（Berlaga）假装自己是印度副王。经过一番思考，他觉得这太冒险了——他们可能会让他骑上大象，并强迫他驾驭这头巨兽穿过街道。他决定换个说辞。他还没想好下一个扮演的角色是什么。在此期间，他正享受着自己最喜欢的消遣：玩纸牌。

他时不时会想：自己获胜的游戏比例是多少？纸牌游戏本身只提供保留两位小数的答案，而贝尔拉加热爱精准，有时会自己计算这个比例。根据比例本身以及所使用的进制，答案既可以是有限小数，也可以是循环小数。没错，疯狂的会计师可以使用他们想要的任何位置记数法（进制），而不仅仅是十进制。例如，在十进制中，$1/3$ 是一个无限循环小数，而 $4/10$ 是一个有限小数；然而，在三进制中，情况正好相反：$1/3$ 是一个有限小数 “0.1”，而 $4/10$ 是一个无限循环小数 “0.101210121012...”。

自然地，像所有会计师一样，他不喜欢无限小数，并且只在绝对确定获胜比例会是有限小数时，才愿意去计算它。为了做到这一点，他需要再多玩几局游戏。

请帮助贝尔拉加找到最少需要额外进行的游戏局数。已进行的游戏总局数不能超过 $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$ —— 贝尔拉加已经进行的游戏局数（$1 \le a_i \le M$）。

输出格式

输出必须包含 $N$ 行，每行对应一个询问的答案。

每个答案必须是一个整数 $A$ —— 为了确保获胜比例是有限小数而需要额外进行的游戏局数（$A \ge 0$）。如果在这种情况下游戏总局数超过了 $M$，则输出 $-1$ 作为答案。

样例

输入样例 1

100 120 3
5
117
13

输出样例 1

0
-1
3