K - K-th Common Divisor

Time limit: 1 s
Memory limit: 128 MiB
Languages: C, C++, Java, Python, ... (details)

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.

Input

The input contains one line with three integers $A$, $B$, $K$ with $1 \leq A, B \leq 100$ and $K ≥ 1$.

The $K$-th largest positive integer that divides both $A$ and $B$ exists.

Output

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

Sample test(s)

Input
8 12 2
Output
2
Input
100 50 4
Output
5
Input
1 1 1
Output
1