题目描述

You are given positive integers $A$ and $B$.

Find the $K$-th largest positive integer that divides both $A$ and $B$.

The input guarantees that there exists such a number.

给你正整数 $A$ 和 $B$ 。

求同时整除 $A$ 和 $B$ 的 $K$ -th 最大正整数。

输入保证存在这样一个数。

输入格式

输入内容按以下格式标准输入：

$A$ $B$ $K$

输出格式

打印同时整除 $A$ 和 $B$ 的 $K$ -th 最大正整数。

样例 #1

样例输入 #1

8 12 2

样例输出 #1

2

样例 #2

样例输入 #2

100 50 4

样例输出 #2

5

样例 #3

样例输入 #3

1 1 1

样例输出 #3

1

说明

数据规模与约定

• 输入值均为整数
• $1 \leq A, B \leq 100$
• 同时除以 $A$ 和 $B$ 的 $K$ -th 最大正整数存在。
• $K \geq 1$

样例 $1$ 解释

三个正整数能同时整除 $8$ 和 $12$ ： $1, 2$ 和 $4$ 。其中，第二大的数是 $2$ 。