Nano's clock hands

Time limit1sMemory limit1024 MB

Summary

Two clocks with N and M ticks have hands moving in opposite directions, and the task asks for the first positive second when both hands point to the same number.

Level: Medium7 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

Inside Nano's head, two small clocks are running. Clock A has ticks $1$ through $N$ drawn in clockwise order, and clock B has ticks $1$ through $M$ drawn the same way. Each hand moves one tick per second. Hand A turns counterclockwise, and hand B turns clockwise.

Right now, both hands point to $1$ . Find the earliest time, in seconds, at which the two hands point to the same integer again.

Input

The first line contains the number of test cases $T$ ( $1\le T\le 100\,000$ ).

Each test case is given as two integers $N$ and $M$ ( $1\le N,M\le 10^{9}$ ).

Output

For each test case, print the answer on its own line.

Examples1

Example 1
Input
```
2
4 3
2011 407
```
Expected output
```
2
1616
```