Migrated from Lutece 132 Coprime

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

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 \leq 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.

Samples

3 
6 9 1 
6 9 2 
6 9 3

Case 1: 1 
Case 2: 5 
Case 3: 7

Resources

The 5th Guangting Cup Central China Invitatio