离目标最近的公因数

题目描述

给定正整数 a、b 和目标数 x。在 a、b 的全部正公因数中选择一个 d，使 |d-x| 最小；若有两个公因数到 x 的距离相同，选择较小的一个。

输入格式

一行输入三个整数 a、b、x，满足 1≤a,b≤10^5、1≤x≤10^9。

输出格式

输出符合要求的正公因数 d。

样例

输入

18 24 4

输出

3