Project Euler #120: Square remainders

_{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

Since this value can be very large, output it modulo

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

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 .