Home

Contest: Task: Related: TaskA TaskC

Score : $200$ points

Problem Statement

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$.

Sample Input 1

8 12 2

Sample Output 1

2

Three positive integers divides both $8$ and $12$: $1, 2$ and $4$. Among them, the second largest is $2$.

Sample Input 2

100 50 4

Sample Output 2

5

Sample Input 3

1 1 1

Sample Output 3

1