Problem Description

Given integers \( N, Q \) and sequences of integers \( A = (A_1, A_2, \ldots, A_Q), B = (B_1, B_2, \ldots, B_Q) \) of length \( Q \).

For each \( k = 1, 2, \ldots, Q \), solve the following problem:

There is an undirected graph with \( N \) vertices and \( N \) edges, where the vertices are numbered from \( 0 \) to \( N-1 \). The \( i \)-th edge \( (0 \le i < N) \) connects vertex \( i \) and vertex \( (A_k \times i + B_k) \mod N \) mutually. Find the number of connected components in this undirected graph.

Input Format

The input is given from the standard input in the following format:

\( N \) \( Q \) \( A_1 \) \( B_1 \) \( A_2 \) \( B_2 \) \( \vdots \) \( A_Q \) \( B_Q \)

Output Format

Output \( Q \) lines. The \( i \)-th line should contain the answer for \( k = i \).

Sample Input and Output

Sample Input #1

6 3
2 1
0 1
1 0

Sample Output #1

2
1
6

Sample Input #2

11 3
9 1
5 3
8 0

Sample Output #2

3
3
2

Sample Input #3

182 3
61 2
77 88
180 55

Sample Output #3

36
14
9

Notes/Hints

Constraints

• \( 1 \le N \le 10^6 \)
• \( 1 \le Q \le 10^5 \)
• \( 0 \le A_k < N \)
• \( 0 \le B_k < N \)
• All inputs are integers

Sample Explanation 1

For \( k = 1 \), the graph is divided into the following 2 connected components:
- Connected component consisting of vertices \( 0, 1, 3, 4 \).
- Connected component consisting of vertices \( 2, 5 \).
Therefore, the answer for \( k = 1 \) is \( 2 \).

Sample Explanation 2

For \( k = 1 \), the graph is divided into the following 3 connected components:
- Connected component consisting of vertices \( 0, 1, 3, 6, 10 \).
- Connected component consisting of vertices \( 2, 5, 7, 8, 9 \).
- Connected component consisting of vertex \( 4 \).
Therefore, the answer for \( k = 1 \) is \( 3 \).

见题面 Input 部分

见题面 Output 部分