Candy Distribution

Time limit1sMemory limit128 MB

Summary

For each pair K and C, find the smallest B up to 1e9 with B*C = K*X + 1 for some positive integer X, or report IMPOSSIBLE.

Level: Medium5 of 10
Topics: Number theory, Math, Binary search, Implementation
Solved: No attempts yet

Problem

At a party with $K$ guests, the candy must be shared fairly, so the number of candies must be a multiple of $K$ - exactly $K \times X$ candies for some positive integer $X$ . Because at least one guest always loses a candy, one extra candy is bought, making the total $K \times X + 1$ candies.

Candy is sold only in bags, and every bag contains exactly $C$ candies, so buying $B$ bags yields $B \times C$ candies. A purchase of $B$ bags is valid when $B \times C = K \times X + 1$ holds for some positive integer $X$ ; in particular the total number of candies is at least $K + 1$ .

Input

The first line contains the number of test cases $t$ ( $0 < t < 100$ ). Each of the next $t$ lines contains two integers $K$ and $C$ separated by a space ( $1 \le K, C \le 10^9$ ). The buyer can never purchase more than $10^9$ bags, so only $1 \le B \le 10^9$ is allowed.

Output

For each test case, print the minimum number of bags $B$ that makes the purchase valid. If no valid number of bags exists within the allowed range, print IMPOSSIBLE instead. Print one answer per line.

Examples1

Example 1

Input

5
10 5
10 7
1337 23
123454321 42
999999937 142857133

Expected output

IMPOSSIBLE
3
872
14696943
166666655