You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

小北和辰辰玩双人飞行棋, 发现棋盘上有一些奇妙的位置，两人的位置居然能够重叠.

题目描述

小北和辰辰掷骰子向前移动, 最开始, 他们站在 0 位置. 小北的骰子每次都是 $a$ , 小北可以向前移动 $a$ 步, 辰辰的骰子每次都是 $b$, 辰辰每次可以向前移动 $b$ 步.

他们发现, 有一些点是两个人共同停留过的点, 他们想知道, 第 $k$ 个两人都停留的点是多少?(不包含起点)

数据格式

输入格式

多组数据

第一行输入一个整数 $t$, 表示有 $t$ 组数据,

接下来每一行一行三个整数 $a, b, k$.

输出格式

输出 $t$ 行, 每行一个整数表示第 $k$ 个两人都停留的点,

样例

2
2 3 1
2 4 2

6
8

样例解释

小北停留的位置是: $2, 4, 6, 8, 10 ...$, 辰辰停留的位置是: $3, 6, 9, 12 ...$, 第一个他们都停留过的点是 $6$.

数据范围

$1 <= t <= 100$

$1<= a, b, k <= 10^6$