Minimum Steps to Achieve Liquid Ratio

You are given two positive integers a and b representing the ratio of two liquids A and B required to fill a tank in a single step. In each step, the tank is filled with a fixed amount of liquid A and liquid B such that the overall ratio is exactly a:b. To achieve the desired ratio exactly, you may need to perform multiple steps.

Your task is to compute the minimum number of steps required such that the cumulative amounts of liquids A and B maintain the ratio a:b. It turns out that if g is the greatest common divisor (GCD) of a and b, then the answer is given by:

\(\frac{a}{g} + \frac{b}{g}\)

Implement a program that reads multiple test cases from standard input (stdin) and prints the result for each test case to standard output (stdout), one result per line.

inputFormat

The first line contains an integer t (\(t \geq 1\)), the number of test cases. Each of the following t lines contains two positive integers a and b (\(1 \leq a, b \leq 10^9\)) separated by a space.

outputFormat

For each test case, output a single integer representing the minimum number of steps required to achieve the desired liquid ratio a:b. Each answer should be on a new line.

## sample

4
1 2
3 5
2 2
7 10

3
8
2
17

</p>