Master Zhu 有一个数字 $n$。他向你提出 $q$ 次询问，第 $i$ 次询问包含一对整数 $(x_i, y_i)$。对于第 $i$ 次询问，Master Zhu 希望你找到最小的非负整数 $k_i$，使得对于 $n$ 的某个质因数 $p$，同余式 $x_i^{k_i} \equiv y_i \pmod p$ 成立，或者判断不存在这样的 $k_i$。
在本题中，我们规定 $0^0 = 1$。
第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 10^8, 1 \le q \le 10^5$)。接下来 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($0 \le x_i, y_i \le 10^9$)。
对于每次询问，在单独的一行中输出答案。如果找到了 $k_i$，则输出它，否则输出 $-1$。
175 2 2 1 2 3
0 3
The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.
This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.
If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.
Guidelines: