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.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.ArrayList;
import java.util.HashMap;
public class A {
	static public void main(String[] args) {
		FastScanner fs = new FastScanner();
		long n= fs.nextLong();
		long k = fs.nextLong();
		ArrayList<Long> d = new ArrayList<>();
		long temp =n;
		for(long i = 2;i*i<=temp;++i) {
			while(temp%i==0) {
				d.add(i);
				temp/=i;
			}
		}
		if(temp>1)d.add(temp);
		HashMap<Long,Integer> hm = new HashMap<>();
		
		for(long i:d) {
			hm.put(i, hm.getOrDefault(i, 1)+1);
		}
		for(long i:d) {
			ArrayList<Long> x = new ArrayList<>();
			for(long j: hm.keySet())
				x.add(j);
			for(long j: x) {
				if((i*j<=n )&& ((n%(i*j))==0))
					hm.put(i*j, hm.getOrDefault(i*j, 1)+1);
			}
		}
		hm.put((long)1, hm.getOrDefault((long)1, 1)+1);
		if(hm.size()<k) {
			System.out.print(-1);
			return;
		}
		ArrayList<Long> ans = new ArrayList<>();
		for(long i : hm.keySet()) {
			ans.add(i);
		}
		Collections.sort(ans);
		long cnt = 1;
		for(long i : ans) {
			if(cnt==k) {
				System.out.print(i);
				return;
			}
			cnt++;
		}
	}
	
	static void sort(int[] a) {
		ArrayList<Integer> l = new ArrayList<>();
		for(int i:a) {
			l.add(i);
		}
		Collections.sort(l);
		for(int i= 0; i< a.length; ++i) {
			a[i] = l.get(i);
		}
	}
	
	static class FastScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		String next() {
			while(!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
				return st.nextToken();
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
    }
}