In this problem we are interested only in prime prime powers, i.e., numbers of the form a^b, where a and b are prime numbers. For a given number n, we want to find the k-th smallest prime prime power greater than n.

입력 형식

The first and only line of the input contains two integers n and k (1 ≤ n ≤ 10¹⁸, 1 ≤ k ≤ 100,000).

출력 형식

The first and only line of output should contain one integer m, such that m is the k-th smallest prime prime power greater than n.

예제 입력 1

22 1

예제 출력 1

25

예제 입력 2

22 2

예제 출력 2

27