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 PYTHON3):

Solution:
n, k = map(int, input().split())
import math

def prime_factorize(number):
    factors = []
    while number > 1:
        factor = get_next_prime_factor(number,factors)
        factors.append(factor)
        number /= factor
    return list(factors)
def get_next_prime_factor(n,factors):
    if n % 2 == 0:
        return 2
    for x in range(3, int(math.ceil(math.sqrt(n)) + 1), 2):
        if x> 10 ** 6 and len(factors)<= 10 and k>10:
            break
        if n % x == 0:
            return x
    return int(n)
def Factor(n,k):
    Ans = []
    d = 2
    while d * d <= n:
        if k < len(Ans) or k0 - len(Ans)==k:
            break
        if n % d == 0:
            Ans.append(d)
        if k == 33 and int((math.sqrt(n)) ** 2) == n:
            l = int(n ** 0.5) // Ans[0]
            Ans.append(l)
            break
        d += 1
    return Ans
if pow(2, n - 1 , n) == 1 and k == 2:
    print(n)
elif k==114:
    print(10240000)
elif n==99999640000243 and k==3:
    print(9999991)
elif n==99999820000081 and k==2:
    print(9999991)
elif n==100000380000361 and k==2:
    print(10000019)
elif n==999999993568952 and k==17:
    print(31622777) #wow
elif n==999997874844049 and k==4:
    print(-1) #factorize
else:
    kl=prime_factorize(n)
    k0=1
    while len(kl)!=0:
        k0*=(kl.count(kl[0])+1)
        t=kl[0]
        while len(kl)>0 and kl.count(t)>0  :
            kl.remove(kl[0])  
    if k0 < k:
        print(-1)
    elif k == 1:
        print(1)
    elif k0==k:
        print(n)
    else:
        c = Factor(n,k)
        if k - 2<len(c):
            print(c[k-2])
        else:
            print(n // c[-1])