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
#include <bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c;
	cin>>a>>b>>c;
	int d=0;
	for(int i=a;i>=1;i--){
		if(a%i==0&&b%i==0){
			c--;
			if(c==0){
				cout<<i<<endl;
				return 0;
			}
		}
	}
}
