K - K-th Common Divisor

Languages: C, C++, Java, Python, Kotlin
Time & Memory limits: (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 1A,B100 and K1.

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
--- Showing first 30 lines (click "Copy" to get full content) ---
Output
2
--- Showing first 30 lines (click "Copy" to get full content) ---
Input
100 50 4
--- Showing first 30 lines (click "Copy" to get full content) ---
Output
5
--- Showing first 30 lines (click "Copy" to get full content) ---
Input
1 1 1
--- Showing first 30 lines (click "Copy" to get full content) ---
Output
1
--- Showing first 30 lines (click "Copy" to get full content) ---