Background

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.

Problem Description

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.

Input Format

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 Format

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

3
3 2
4 4
5 5

1
3
2

5
4 3
4 4
4 5
4 6
4 7

2
3
3
4
4

3
1145 1499
12344 123456
114514 1919810

2
41
17

Hint

[Sample #1 Explanation]

Query 1:

Query 2:

Query 3:

So the answers are $1, 3, 2$.

[Constraints]

This problem uses bundled testdata.

• 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