同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21975_Coprime

2022-5-16 18:20| 发布者: Hocassian| 查看: 24| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-895068898599-Problem List-采集的数据-后羿采集器.html

Pro.ID

21975

Title

Coprime

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21975

AC

Submit

Ratio

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

描述

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.

输入

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⁹).

输出

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⁹).

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

Hint

case 2: