Dev-The Mad King

0

0 votes
Problem


Dev is a foolish king, ruling over the planet known as Midgard. He loves to paint and recently, he made a masterpiece (shown in the picture below) and wanted to sell it in an auction. But he is wondering how much the base price K (always greater than 0) should be kept so that he does not incur any losses. The king is not greedy so he also does not want to keep the price too high.

                                       

 

In Midgard, the currency system is also a bit unique. There are only 2 types of coins available having values a and b (a and b are coprime). Now the king wants to keep the base price as low as possible, such that any amount greater than or equal to the base price can be achieved by using these two types of coins (a and b).

 

But as mentioned above, the king is so foolish therefore, he isn't able to figure out the base price of his so-called masterpiece. So, he gave you the task to find out the base price for his masterpiece and he will give you a good amount of money for that.

 

Input:

First-line contains a single integer T number of test cases.

Next T lines contain 2 integers a and b (a and b are coprime). Where a and b represent the values of two different types of coins.

 

Output:

Print T lines each contain a single integer K the base price for the painting such that any amount greater than or equal to K can be achieved using some number of coins (can be 0) of type a and some number of coins (can be 0) of type b.

Constraints:

  • 1T3105
  • 1a,b105

 

Time Limit: 1.5
Memory Limit: 256
Source Limit:
Explanation

In the second test case we have two types of the coin a of value 3 and coin b of value 5 using these two types of coins we can make any number greater than or equal to 8
Like 20 = 5+5+5+5,
17=5+3+3+3+3,

Likewise, we can make any number that is greater than or equal to 8.

 

Editor Image

?