C. 【J】T3小清新签到题

给定 q 次查询，每次给定正整数 n,m,k，求出第 k 小的满足仅能被 n,m 中的一个数整除的正整数。保证 n\ne m。

第一行一个整数 q。

第 2 至 q+1 行，每行三个正整数 n,m,k。

输出 q 行，第 i 行输出第 i 个查询的答案。

数据范围：

第 1 个测试点分值为 10\text{pts}，满足 k=1。

第 2 个测试点分值为 15\text{pts}，满足 n,m,k\le 100。

第 3 个测试点分值为 10\text{pts}，保证 n|m。（m是n的倍数）

第 4 个测试点分值为 55\text{pts}。以上的测试点均满足 q\le 100。

第 5 个测试点分值为 10\text{pts}。

对于所有测试数据，均满足 q\le 10^5,1\le n,m\le 10^8,1\le k\le 10^{10}​。