题目描述

为弥补兵力的不足，刘关张三人准备去抓 $K$ 个壮丁。

简单粗暴，他们将村民按体质从 $1\sim N$ 编号，为了给村庄保留一定劳动力，他们提出了自己的观点：

• 关羽认为编号为 $A$ 的倍数的人应当被抓走；
• 张飞认为编号为 $B$ 的倍数的人不应当被抓走；
• 刘备认为两个兄弟说的都应当满足，并且优先抓小号。

由于刘备是老大，自然听刘备的。

输入描述

第一行是一个整数 $T$ 代表测试数据的组数。

接下来 $T$ 行每行包含三个整数 $A,B,K$，意义如题目描述所示。

输出描述

对每组测试用例，输出第 $K$ 号壮丁的编号。如果无法完成抓壮丁，输出 -1。

2
3 2 4
10 2 1

21
-1

第一个测试数据壮丁依次为 3,9,15,21。

评测用例规模与约定：

对于 30% 的评测用例，$1 ≤A,B≤ 100，1 ≤K≤ 10^5$。

对于所有评测用例，$1≤T≤10，1≤A,B≤10^9，1≤K≤10^9$。