Number of Passes in a Circular Ball Game

There are N friends sitting in a circle. Starting from a designated person, a ball is passed to the right by moving K positions. The process continues until the ball returns to the starting person.

You are required to determine the number of passes needed for the ball to make one complete round and return to its original holder.

Mathematically, you must find the smallest positive integer \(m\) such that:

\(m \times K \equiv 0 \pmod{N}\)

This is equivalent to:

\(m = \frac{N}{\gcd(N,K)}\)

inputFormat

The input begins with an integer T representing the number of test cases. Each of the following T lines contains two space-separated integers N and K:

• N: the total number of friends.
• K: the number of steps to pass the ball to the right.

outputFormat

For each test case, output a single integer on a new line, which is the number of passes required for the ball to return to the starting person.

## sample

3
5 2
6 1
10 3

5
6
10

</p>