- All Contests
- ProjectEuler+
- Project Euler #120: Square remainders

# Project Euler #120: Square remainders

# 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

**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 .