Problem Statement

You are given integers $N$ and $Q$, and two integer sequences of length $Q$: $A=(A_1,A_2,\ldots,A_Q)$ and $B=(B_1,B_2,\ldots, B_Q)$.

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

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

Constraints

• $1 \le N \le 10^6$
• $1 \le Q \le 10^5$
• $0 \le A_k < N$
• $0 \le B_k < N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 B_1
A_2 B_2
\vdots
A_Q B_Q

Output

Print $Q$ lines. The $i$-th line should contain the answer for $k=i$.