Minimum Bucket Filling Steps

You are given a desired ratio of apples to bananas for a bucket. Your task is to compute the minimum number of steps required to fill the bucket with apples and bananas such that the ratio matches the desired ratio.

For each test case, you are provided two integers \(m\) and \(n\). The answer for a test case is computed as follows: first, reduce the fraction \(\frac{m}{n}\) to its simplest form by dividing both the numerator and the denominator by their greatest common divisor (gcd), and then sum the resulting numerator and denominator. In formula form:

\[ \text{steps} = \frac{m}{\gcd(m,n)} + \frac{n}{\gcd(m,n)} \]

Print each result on a new line.

inputFormat

The first line contains a single integer \(T\) representing the number of test cases. Each of the next \(T\) lines contains two space-separated integers \(m\) and \(n\) which represent the desired ratio of apples to bananas.

outputFormat

For each test case, output the minimum number of steps needed to achieve the desired ratio, each on a new line.

## sample

3
1 1
3 2
5 3

2
5
8

</p>