P10515 Spinning in Circles

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.

The first line contains a positive integer $T$, representing the number of queries. For each query, one line contains two positive integers $n, m$.

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

**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