A137131.同步钟声

科技节开幕式上有两座自动钟。

第一座钟每隔 $a$ 分钟响一次，第二座钟每隔 $b$ 分钟响一次。也就是说，在正整数时刻中，第一座钟会在 $a,2a,3a,\ldots$ 时刻响，第二座钟会在 $b,2b,3b,\ldots$ 时刻响。

如果两座钟在同一时刻同时响，那么这个时刻只计算一次。

现在有 $T$ 次询问。每次给定 $a,b,k$，请你求出第 $k$ 个至少有一座钟响起的正整数时刻。

第一行输入一个整数 $T$，表示询问次数。

接下来 $T$ 行，每行输入三个整数 $a,b,k$。

对于每次询问，输出一个整数，表示答案。

数据范围

$1\le T\le 10^4$

$1\le a,b,k\le 10^9$

答案不超过 $10^{18}$，请使用 long long。