H. The Revolving Death Clock
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In one of the Squid Game challenges, a Revolving Death Clock determines the fate of the players. The clock consists of two circular gears: a smaller gear (the Death Gear) rotates around a larger circular base (the Clock Gear).

The Death Gear starts at a specific point on the Clock Gear and rotates around it. Your task is to determine the minimum number of full rotations the Death Gear completes before returning to its starting position relative to the Clock Gear. You are given two circles:

  • The Clock Gear with diameter $$$D_{1}$$$
  • The Death Gear with diameter $$$D_{2}$$$
The Death Gear rolls without slipping along the edge of the Clock Gear. Determine the minimum integer number of complete rotations the Death Gear makes around itself before returning to its initial position.
This is an example of how the gear rotates.
Input

The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^{6} $$$)

Each test case contains :

Two integers $$$D_{1}$$$ and $$$D_{2}$$$ ($$$1 \leq D_{2} \leq D_{1} \leq 10^{9} $$$), representing the diameters of the Clock Gear and the Death Gear, respectively.

Output

For each test case, output a single integer, the minimum integer number of complete rotations the Death Gear makes around itself before returning to its starting position.

Example
Input
2
1 1
3 1
Output
2
4
Note

The first test case: here.