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.

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.

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

Input

8 12 2

Output

2

Input

100 50 4

Output

5

Input

1 1 1

Output

1