题目描述

给定正整数 $N,M,K$，求出第 $K$ 小的满足仅能被 $N,M$ 中的一个数整除的正整数。

$1 \le N,M \le 10^8,1 \le K \le 10^{10}$,$N!=M$。

输入格式

按照如下格式输入：

$N$ $M$ $K$

输出格式

一个整数，表示答案

样例 #1

样例输入 #1

2 3 5

样例输出 #1

9

样例 #2

样例输入 #2

1 2 3

样例输出 #2

5

样例 #3

样例输入 #3

100000000 99999999 10000000000

样例输出 #3

500000002500000000

提示

数据范围

• $1\leq\ N,\ M\leq\ 10^8$
• $1\leq\ K\leq\ 10^{10}$
• $N\neq\ M$