# Coprime

Time Limit: 5000 ms

Memory Limit: 65535 ms

## Description

Please write a program to calculate the k-th 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 k-th 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

## Source

The 5th Guangting Cup Central China Invitatio