题目描述
Background
A little frog is trapped in a dark cell of the prison, enduring unending torment, both physically and mentally.
His spirit is depressed, and his movements are sluggish.
Some forces are temporarily suppressed, but the more they are suppressed, the greater their rebound.
He needs a turning point.
Problem Description
The frog has $m+1$ undirected graphs, numbered from $0$ to $m$. Each graph has the same vertex set $V$, which contains $n$ vertices numbered from $0$ to $n-1$. Initially, all graphs have no edges.
Next, in the graph numbered $x$, for all vertices $i$ in the range $[0, n-1]$, the frog will connect vertex $i$ with vertex $(i \cdot x) \bmod n$ with an undirected edge.
He wants to know how many of these $m+1$ graphs are connected. This question is for you to answer.
Notes:
1. $\bmod$ denotes the modulo operation, where $a \bmod b$ represents the remainder of $a$ divided by $b$.
2. In a graph, if there exists at least one path between any two distinct vertices $x$ and $y$ in the vertex set, we call the graph connected.
Input Format
This problem contains multiple test cases.
The first line contains an integer $T$, representing the number of test cases.
The next $T$ lines, each containing two integers $n$ and $m$, have the same meaning as described above.
Output Format
Output $T$ lines, each containing an integer representing the answer.
Sample Input and Output
Sample Input #1
3
3 2
4 4
5 5
Sample Output #1
1
3
2
Sample Input #2
5
4 3
4 4
4 5
4 6
4 7
Sample Output #2
2
3
3
4
4
Sample Input #3
3
1145 1499
12344 123456
114514 1919810
Sample Output #3
2
41
17
Notes
[Sample #1 Explanation]
Query 1:
| Graph Number | Edge Set | 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 | 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 | 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 |
Thus, the answers are $1, 3, 2$ respectively.
[Data Range and Constraints]
This problem is grouped into bundled test cases.
| Subtask | Data Range | 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 data, it is guaranteed that $1 \le T \le 5, 1 \le n, m \le 10^{14}$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分