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:
def MillerRabin(n):
    d = minus_one = n - 1
    for s in range(100000):
        if d & 1:
            for a in 2, 3, 5, 7, 11, 13, 17:
                a = pow(a, d, n)
                if a != 1:
                    for _ in range(s):
                        if a == minus_one:
                            return True
                        a = a * a % n
                    else:
                        return False
            return True
        d //= 2


def factor(x):
    res, p, steps = {}, 2, (1, 2, 2, 4, 2)
    while True:
        if x < p * p:
            if x != 1:
                res[x] = 1
            return res
        for s in steps:
            while not x % p:
                x //= p
                res[p] = res.get(p, 0) + 1
            p += s
        steps = (4, 2, 4, 6, 2, 6, 4, 2)


from math import sqrt


def main():
    n, k = map(int, input().split())
    if k == 1:
        print(1)
        return
    if MillerRabin(n):
        print(n if k == 2 else -1)
        return
    r = int(sqrt(n))
    if r * r == n and MillerRabin(r):
        print({1: 1, 2: r, 3: n}.get(k, -1))
        return
    divisors = [1]
    if k < 26881:
        for p, v in factor(n).items():
            divisors += [p * q for p in [p ** i for i in range(1, v + 1)] for q in divisors]
    print(-1 if len(divisors) < k else sorted(divisors)[k - 1])


if __name__ == '__main__':
    main()