Circle Cells Visitation

Little \(\delta\) loves to spin in circles. He has a circle that is evenly divided into \(n\) cells, where \(n\) is a prime number. Each cell \(i\) (with \(1 \leq i \leq n\)) contains a number equal to \(i \times m\). Initially, Little \(\delta\) stands on cell 1.

Then he repeatedly performs the following steps:

1. He looks at the number written on the cell he is currently on.
2. He moves forward by that many cells (wrapping around the circle if necessary).

Formally, if he is on cell \(i\), he reads the value \(i \times m\) and then moves to cell \(i + i\times m\) modulo \(n\) (with the convention that a remainder of 0 corresponds to cell \(n\)).

It can be shown that if you represent the cell indices modulo \(n\) (where cell \(n\) corresponds to 0), the process is equivalent to the recurrence:

\(a_0 = 1,\quad a_{k+1} \equiv (m+1)\,a_k \pmod{n}\).

The task is to determine the total number of distinct cells that Little \(\delta\) will have stepped on eventually (i.e. the size of the cycle he enters). Note that there are two special cases:

• If \((m+1) \equiv 1 \pmod{n}\), then he always remains on cell 1, and the answer is 1.
• If \((m+1) \equiv 0 \pmod{n}\), then after the first move he lands on cell \(n\) (represented as 0 modulo \(n\)) and remains there, so the answer is 2 (cells 1 and \(n\)).

inputFormat

The first line of input contains a single integer \(T\) denoting the number of test cases.

Each of the following \(T\) lines contains two space-separated integers \(n\) and \(m\) where \(n\) is a prime number and \(m\) is the multiplier.

outputFormat

For each test case, output a single integer representing the number of distinct cells that Little \(\delta\) steps on.

sample

5
7 2
7 6
5 0
11 2
13 4

6
2
1
5
4