문제2058--Candy Distribution

2058: Candy Distribution

실행시간 제한: 10 Sec  메모리사용 제한: 128 MB
제출: 32  통과: 8
[제출] [채점기록] [묻고답하기]

문제 설명

Kids like candies, so much that they start beating each other if the candies are not fairly distributed. So on your next party, you better start thinking before you buy the candies.

If there are K kids, we of course need K · X candies for a fair distribution, where X is a positive natural number. But we learned that always at least one kid looses one candy, so better be prepared with exactly one spare candy, resulting in (K · X) + 1 candies.

Usually, the candies are packed into bags with a fixed number of candies C. We will buy some of these bags so that the above constraints are fulfilled.

입력 설명

The first line gives the number of test cases t (0 < t < 100).

Each test case is specified by two integers K and C on a single line, where K is the number of kids and C the number of candies in one bag (1 ≤ K, C ≤ 109). As you money is limited, you will never buy more than 109 candy bags.

출력 설명

For each test case, print one line. If there is no such number of candy bugs to fulfill the above constraints, print IMPOSSIBLE instead. Otherwise print the number of candy bags, you want to buy. If there is more than one solution, any will do.

입력 예시 Copy

5
10 5
10 7
1337 23
123454321 42
999999937 142857133

출력 예시 Copy

IMPOSSIBLE
3
872
14696943
166666655