주 선생님과 근

시간 제한3초메모리 제한512 MB

요약

각 질의 (x, y)마다 n의 어떤 소인수 p에 대해 x^k ≡ y (mod p)를 만족하는 가장 작은 k ≥ 0을 구하고, 없으면 -1을 출력한다.

난이도: 어려움10점 중 9점
유형: 정수론, 수학, 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

주 선생님에게 수 $n$ 이 있다. 그는 여러분에게 $q$ 개의 질의를 한다. $i$ 번째 질의는 정수 쌍 $(x_i, y_i)$ 이다. $i$ 번째 질의에서 여러분은 $n$ 의 소인수 $p$ 가운데 하나에 대해 $x_i^{k_i} \equiv y_i \pmod p$ 가 성립하도록 하는 가장 작은 음이 아닌 정수 $k_i$ 를 찾거나, 그러한 $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$ 를 찾았다면 $k_i$ 를 출력하고, 찾지 못했다면 $-1$ 을 출력한다.

예제1

예제 1
입력
```
175 2
2 1
2 3
```
예상 출력
```
0
3
```