Once Tanay and Sid were returning from work in train, both tired and hungry. They wanted to buy some food.They saw Bansal, the seller, and wanted to buy the last food packet he had. Bansal didn’t want to sell the packet but couldn’t refuse. Probably he was hungry too. Bansal proposed “I will not charge more than 10^18 rupees for the food but you must give the exact change for the amount i say.” Tanay and Sid had magical purses. Tanay’s purse could produce any number of coins of denomination A and Sid’s purse could produce any number of coins of denomination B. So they agreed. Alas, both A and B were known to Bansal. Bansal set the price to a value in his own bounds(<=10^18) such that Tanay and Sid could not pay for it together. Can you tell the minimum price and maximum price that Bansal can ask for? Note that minimum will not be zero until forced as Bansal will try not to give it for free.

Input

First line contains a single integer t: no. of test cases.
Next t lines contains two integers A and B for respective test cases.

Output

A single line for each test case containing a single integer answer, the price set by Bansal, the seller.

Constraints

1 ≤ t ≤ 100000
1 ≤ A, B ≤ 10⁹