시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 74 17 12 20.339%

문제

In this problem we are interested only in prime prime powers, i.e., numbers of the form ab, 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 ≤ 1018, 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