Description
There are N stones in a circle, numbered from 0 to N-1. And there are k coins on the kth stone (For example, there are two coins on the stone with number 1). Now, Lasercat wants to collect as many coins as he can. However, he can leap over exactly L stones in a single step, which means he can jump from stone (j mod n) to stone ((j+L) mod n).
Lasercat starts from stone numbered 0 and he can jump as many times as he want. So how many coins can he collect in the end?
Input
The first line contain a single number C (1<=C<=1000) which means the number of test cases.
Then C lines follow, each line has two integers N(1<=N<=1000000) and L(1<=L<=1000000)
Output
For each test case, you should output two lines.
The first line is "Case #:", # means the number of the test case.
The second line output the number of the coins Lasercat can collect.
Sample Input
1
2 1
Sample Output
Case 1:
3