Problem Description

Little $\delta$ likes spinning in circles.

He has a circle that is evenly divided into $n$ cells. Magically, $n$ is a prime number. On the $i$-th cell, there is a number written as $i \times m$. He is now standing on the first cell.

Next, he will look at the number under his feet, then move forward by that many cells. He will keep repeating this.

Find the number of distinct cells that Little $\delta$ has stepped on in the end. Since Little $\delta$ has many circles, he will ask you many times.

Input Format

The first line contains a positive integer $T$, representing the number of queries.

For each query, one line contains two positive integers $n, m$.

Output Format

For each query, output one line with one positive integer, representing the number of cells that have been stepped on.

6
5 2
11 10
17 12
23 8
31 12
9999901 114514

4
2
4
11
30
16260

Hint

Sample Explanation

Take the first query as an example. The cell indices that Little $\delta$ visits in order are $1 \to 3 \to 4 \to 2 \to 1 \to \cdots$, so the number of distinct cells stepped on is $4$.

Constraints

• For $20\%$ of the testdata, $n \le 10^3$, $T \le 2 \times 10^3$.
• For another $40\%$ of the testdata, $T \le 3 \times 10^3$.
• For the remaining $40\%$ of the testdata, there are no special properties.

For all testdata, $1 \le m < n \le 10^7$, $1 \le T \le 4 \times 10^5$. It is guaranteed that $n$ is prime.

Translated by ChatGPT 5