题目描述

定义 $\operatorname{xcm}_k(x,y)$ 为 $x$ 和 $y$ 的第 $k$ 小公倍数。例如：$\operatorname{xcm}_1(x,y)=\operatorname{lcm}(x,y)$。给出正整数 $x,y,k$，求 $\operatorname{xcm}_k(x,y)$。

输入格式

本题采用多测，第一行输入数据组数 $T$。

接下来 $T$ 行，每行 $3$ 个正整数 $x,y,k$。

输出格式

输出 $T$ 行，每行一个正整数，代表 $\operatorname{xcm}_k(x,y)$。

2
5 9 1
6 8 2

45
48

提示

样例解释 1

$\operatorname{xcm}_1(5,9)=\operatorname{lcm}(5,9)=45$。

数据范围

对于 $100\%$ 的测试数据，$1\le T\le10$，$1\le x,y,k\le 2\times{10}^6$。