시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB255416.667%

문제

Master Zhu has a number $n$. He asks you $q$ queries, the $i$-th query is a pair of integers $(x_i, y_i)$. For $i$-th query, Master Zhu would like you to find the smallest non-negative integer $k_i$ such that, for some $p$ which is a prime divisor of $n$, the equivalence $x_i^{k_i} \equiv y_i$ modulo $p$ holds, or to determine that no such $k_i$ exists.

In this problem, we consider that $0^0 = 1$.

입력

The first line of input contains two integers $n$ and $q$ ($1 \le n \le 10^8$, $1 \le q \le 10^5$). Each of the next $q$ lines contains two integers $x_i$ and $y_i$ ($0 \le x_i, y_i \le 10^9$).

출력

For each query, print the answer on a separate line. If you found $k_i$, print it, otherwise print the number $-1$.

예제 입력 1

175 2
2 1
2 3

예제 출력 1

0
3