p03106 AtCoder Beginner Contest 120 - K-th Common Divisor
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.

Constraints

* All values in input are integers.
* 1 \leq A, B \leq 100
* The K-th largest positive integer that divides both A and B exists.
* K \geq 1

Input

Input is given from Standard Input in the following format:


A B K


Output

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

Examples

Input

8 12 2


Output

2


Input

100 50 4


Output

5


Input

1 1 1


Output

1
```python
A,B,K = map(int,input().split())
L = []
for i in range(1,101):
  if A%i == 0 and B%i == 0:
    L.append(i)
print(L[len(L)-K])
```