Problem: You are given two integers n and k. Find k-th smallest divisor of n, or report that it doesn't exist.

Divisor of n is any such natural number, that n can be divided by it without remainder.

Input

The first line contains two integers n and k (1 ≤ n ≤ 1015, 1 ≤ k ≤ 109).

Output

If n has less than k divisors, output -1.

Otherwise, output the k-th smallest divisor of n.

Examples

Input

4 2


Output

2


Input

5 3


Output

-1


Input

12 5


Output

6

Note

In the first example, number 4 has three divisors: 1, 2 and 4. The second one is 2.

In the second example, number 5 has only two divisors: 1 and 5. The third divisor doesn't exist, so the answer is -1.

Solution (in JAVA):

Solution:
import java.util.*;

public class Delitel2{
	static	ArrayList<Long> number = new ArrayList<Long>();
	static	long n=0;
	static ArrayList<ArrayList<Long>> primeNum = new ArrayList<ArrayList<Long>>();	
	static int a=-1;

	public static void main(String[] args){
		long k=0,l=1;
		int r,oh=0,coh=0;
		Scanner sc = new Scanner(System.in);
		n = sc.nextLong();
		k = sc.nextLong();
		prostNum();
		for(int j=0;j<a;j++)
			for(int i=j+1;i<=a;i++){
				for(Long lonj:primeNum.get(j)){
					for(Long loni:primeNum.get(i)){	
						l=lonj*loni;
						number.add(l);
					}
				}
				for(int g=i+1;g<=a;g++){
					r = number.size();
					for(Long longi:primeNum.get(g))
						for(int h=oh;h<r;h++){
							l=number.get(h)*longi;
							number.add(l);
						}
				}
				oh=number.size();
			}
		for(int i=0;i<=a;i++)
				for(Long loni:primeNum.get(i))
					number.add(loni);
		number.add(1l);
		Collections.sort(number);
		//sort();
		if(n==1){
			number.clear();
			number.add((long)1);
		}
		if(number.size()>=k)
			System.out.println(number.get((int)k-1));
		else System.out.println(-1);
	}//main
	public static void prostNum(){
		boolean pr = true;
		long f=n;
		int l=1;
		for(long i=2;i<=f;i++){
			if(f%i==0){
				a++;
				primeNum.add(new ArrayList<Long>());
				l=1;
				while(true){
					if(f%i==0)
						primeNum.get(a).add((long)Math.pow(i,l));
					else break;
					f=f/i;
					l++;
				}
			}//f%i==0
			else{
				pr = true;
				for(long j = 2;j<(long)Math.sqrt(f)+1;j++)
					if(f%j==0){
						pr = false;
						i=j-1;
						break;
					}
				if(pr){
					i=f-1;
				}
			}
		}
	}
}//class