{"raw_statement":[{"iden":"problem statement","content":"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)$.\nFor each $k=1,2,\\ldots,Q$, solve the following problem:\n\n> 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."},{"iden":"constraints","content":"*   $1 \\le N \\le 10^6$\n*   $1 \\le Q \\le 10^5$\n*   $0 \\le A_k < N$\n*   $0 \\le B_k < N$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $Q$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_Q$ $B_Q$"},{"iden":"sample input 1","content":"6 3\n2 1\n0 1\n1 0"},{"iden":"sample output 1","content":"2\n1\n6\n\nFor $k=1$, the graph has the following two connected components:\n\n*   A connected component with vertices $0,1,3,4$.\n*   A connected component with vertices $2,5$.\n\nThus, the answer for $k=1$ is $2$."},{"iden":"sample input 2","content":"11 3\n9 1\n5 3\n8 0"},{"iden":"sample output 2","content":"3\n3\n2\n\nFor $k=1$, the graph has the following three connected components:\n\n*   A connected component with vertices $0,1,3,6,10$.\n*   A connected component with vertices $2,5,7,8,9$.\n*   A connected component with vertex $4$.\n\nThus, the answer for $k=1$ is $3$."},{"iden":"sample input 3","content":"182 3\n61 2\n77 88\n180 55"},{"iden":"sample output 3","content":"36\n14\n9"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}