Matcom Online Grader

ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.

Matcom Grader Speed Contest - 2019

Ended

Overview
Problems
Standing
Submissions
Submit
Clarifications
Virtual participation

Register

Are you sure you want to participate in this contest ? If you select a team then virtual participation for other team members will be disabled. So, pick one if and only if your teammates are ready to compete with you.

K - K-th Common Divisor

Languages: C, C++, Java, Python, Kotlin, C#

Time & Memory limits: (details)

You are given positive integers

A $A$ and

B $B$ . Find the

K $K$ -th largest positive integer that divides both

A $A$ and

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

Input

100 50 4

Output

Input

1 1 1

Output