P10394 Nonstop!

The little frog was locked in a small dark room in prison, suffering nonstop torture, both physically and mentally. His mind is exhausted, and his body moves slowly. Some things have been temporarily suppressed, but the more they are suppressed, the stronger the backlash will be when they rebound. He needs a trigger.

The frog has $m + 1$ undirected graphs, numbered $0 \sim m$. The vertex set of each graph is $V$, and $V$ contains $n$ vertices numbered $0 \sim n - 1$. At the beginning, none of the graphs has any edges. Next, in the graph with number $x$, for every $i$ in $[0, n - 1]$, the frog will connect vertex $i$ and vertex $(i \cdot x) \bmod n$ with an undirected edge. He wants to know, among these $m + 1$ graphs, how many graphs are **connected**. Please answer this question. Notes: 1. $\bmod$ means modulo. $a \bmod b$ is the remainder when $a$ is divided by $b$. 2. In a graph, if for any two different vertices $x, y$ in the vertex set there exists at least one path between them, then we call this graph **connected**.

**This problem contains multiple test cases**. The first line contains an integer $T$, which is the number of test cases. The next $T$ lines each contain two integers $n, m$, with the same meaning as above.

Output $T$ lines. Each line contains one integer, the answer for that test case.

**[Sample #1 Explanation]** Query 1: | Graph number | Edge set | Is the graph connected | | :------: | :-----------------: | :--------: | | $0$ | $(0,0),(1,0),(2,0)$ | Yes | | $1$ | $(0,0),(1,1),(2,2)$ | No | | $2$ | $(0,0),(1,2),(2,1)$ | No | Query 2: | Graph number | Edge set | Is the graph connected | | :------: | :-----------------------: | :--------: | | $0$ | $(0,0),(1,0),(2,0),(3,0)$ | Yes | | $1$ | $(0,0),(1,1),(2,2),(3,3)$ | No | | $2$ | $(0,0),(1,2),(2,0),(3,2)$ | Yes | | $3$ | $(0,0),(1,3),(2,2),(3,1)$ | No | | $4$ | $(0,0),(1,0),(2,0),(3,0)$ | Yes | Query 3: | Graph number | Edge set | Is the graph connected | | :------: | :-----------------------: | :--------: | | $0$ | $(0,0),(1,0),(2,0),(3,0),(4,0)$ | Yes | | $1$ | $(0,0),(1,1),(2,2),(3,3),(4,4)$ | No | | $2$ | $(0,0),(1,2),(2,4),(3,1),(4,3)$ | No | | $3$ | $(0,0),(1,3),(2,1),(3,4),(4,2)$ | No | | $4$ | $(0,0),(1,4),(2,3),(3,2),(4,1)$ | No | | $5$ | $(0,0),(1,0),(2,0),(3,0),(4,0)$ | Yes | So the answers are $1, 3, 2$. --- **[Constraints]** **This problem uses bundled testdata.** | $\text{Subtask}$ | Constraints | Score | | :---: | :---: | :---: | | $1$ | $n, m \le 200$ | $15$ | | $2$ | $n, m \le 3000$ | $30$ | | $3$ | $n, m \le 10^7$ | $15$ | | $4$ | $n \le 3000, m \le 10^{14}$ | $15$ | | $5$ | $n, m \le 10^{14}$ | $25$ | - For $100\%$ of the testdata, it is guaranteed that $1 \le T \le 5$ and $1 \le n, m \le 10^{14}$. Translated by ChatGPT 5