Time Limit:3000ms Memory Limit:65536KB

Description

Please write a program to calculate the kth positive integer that is coprime
with m and n simultaneously. A is coprime with B when their greatest common
divisor is 1.

Input
The first line contains one integer T representing the number of test cases.
For each case, there's one line containing three integers m, n and k (0 < m, n, k
<= 10^9).

Output
For each test case, in one line print the case number and the kth positive
integer that is coprime with m and n.
Please follow the format of the sample output.

Sample Input
3
6 9 1
6 9 2
6 9 3

Sample Output
Case 1: 1
Case 2: 5
Case 3: 7

Hint

Author

Source
