题目描述

小婷正在为珅泽教育的编程训练整理“【GESP强化 二级】第K个公约数”任务，小泽负责把实际要求准确转换成程序。每一组输入都代表一次独立任务，程序必须严格遵守下面给出的规则，并按指定格式给出结果。

在核对方案时，他们发现即使任务看起来不长，边界情况、处理顺序和输出格式也同样重要。请认真阅读完整条件，帮助小泽完成这次训练。

给定两个正整数 $A,B$ 和正整数 $K$。把 $A$ 与 $B$ 的所有公约数按从大到小排列，请输出其中第 $K$ 个公约数。

输入格式

一行包含三个整数 $A,B,K$。

输出格式

输出第 $K$ 大的公约数。

8 12 2

2

100 100 9

1

1 1 1

1

数据范围与约定

• $1 \le A,B \le 100$
• $K$ 不超过 $A,B$ 的公约数数量