This problem is a programming version of Problem 120 from projecteuler.net
Consider the remainder when is divided by .
For example, if , and , then , so the remainder is . And as varies, so too will the remainder, but for and it turns out that the maximum remainder is .
Let be the largest remainder when is divided by , among all .
Given and , find
Input Format
The first line of input contains , the number of test cases.
Each test case consists of a single line containing two integers, and .
Constraints
For test cases worth of the total score, .
For test cases worth of the total score, .
For test cases worth of the total score, .
Note is calculated as 1.
Output Format
For each test case, output a single line containing the requested sum modulo .
Sample Input
1
2 2
Sample Output
2
Explanation
and , so we want .
is simply , because , and the remainder of anything when divided by is .
is , which can be obtained for example with :
Thus, the answer is , and modulo this is simply .