题面

给定两个不同的正整数 $p, q$。对于一个正整数 $x$，我们说它是美丽数，当且仅当 $x$ 被 $p$ 与 $q$ 中恰好一个整除。

再给定正整数 $k$，你需要找到第 $k$ 小的美丽数。

输入格式

本题有多组评测数据。

第一行一个正整数 $T$，表示数据组数。

接下来 $T$ 行，每行三个正整数 $p, q, k$。

输出格式

共 $T$ 行，每行一个正整数，表示找到的第 $k$ 小的美丽数。

由数据范围可知，本题答案在可表示的范围内。

样例

输入 #1

5
9 1 3
9 8 3
1 8 10
7 2 7
1 10 9

输出 #1

3
16
11
12
9

输入 #2

5
864046 547536 615658
194705 528497 461026
68849 642182 675632
723337 935889 100891
789764 282979 527046

输出 #2

206340036672
65597282730
42012417139
41163661996
109800662643

输入 #3

5
34776644 71536530 2463573204
23420039 58019478 3591531289
17078574 15585508 1995221251
50322730 91184106 1495554529
11358271 76454670 636131563

输出 #3

57649287412010896
59924705282832701
16258977349676334
48496252726221980
6290782595910270

数据范围

\begin{array}{|c|c|c|} \hline \textbf{Subtask} & \max T & \max p, q & \max k & \textbf{Score} \\ \hline 1 & 5 & 10^3 & 10^2 & 20 \\ \hline 2 & 5 & 10^6 & 10^6 & 30 \\ \hline 3 & 10^5 & 10^8 & 10^{10} & 50 \\ \hline \end{array}

本题 Subtask 内捆绑测试。