It's end semester time and John and Joey are super happy since tomorrow is their last exam, and they have a long winter break after that. Unfortunately, this last exam also happens to be an HM exam, and as a result they have a large number of readings to read. Since they are taking different HM courses, they have different sets of readings to read. But they find that, surprisingly, all of John's readings have A pages in them (1 <= A <= 10⁹), and all of Joey's readings have exactly B pages in them (1 <= B <= 10⁹). Even more surprising, they find that even though their courses and readings are totally different, they have exactly the same number of pages to read!

So they decide to sit and study together, so that they don't get bored and accidentally fall asleep. Luckily, both have the same reading speed, so since they start studying together, they will also complete their readings at exactly the same time, and will finally be able to get some sleep. But they are wondering how long this might take, and unfortunately, they are too tired to calculate this themselves.

Please help them out ! You are given that both John and Joey take exactly one unit of time to complete one page of their reading. Please print out the minimum possible units of time that they might take to complete their work.

(NOTE: The total amount of time required is nothing but the total number of pages assigned to either of them. What is the minimum possible value of the total pages? Please print this out.)

Input

In the first line we have a single integer T - the number of test cases (T <= 10000). Then T test cases follow.

Each test case consists of exactly one line containing 2 space separated numbers - A and B, where A is the number of pages in each of John's readings, and B is the number of pages in each of Joey's readings. (1 <= A, B <= 10⁹)

Output

For each test case, on a single line, print a positive integer indicating the minimum possible amount of time it might take John and Joey to complete studying.

Example

Input:
6
1 12
12 12
30 14
13 33
86 62
17 78

Output:
12
12
210
429
2666
1326

Explanation

For the first case, since each of John's readings contains just one page, and each of Joey's readings contains exactly 12 pages, the minimum possible value of P (where P is the total number of pages assigned to any one of them) is 12, wherein John has 12 one-page readings, and Joey has just one reading consisting of 12 pages.

For the second test case, since both of them have readings of the same length, the minimum possible amount of time would be if both had just one reading each to read.