Problem Description

For a given number \( n \), find the \( k \)-th smallest \( a^b \) (where both \( a \) and \( b \) are prime numbers) such that its value is greater than \( n \).

Input Format

A single line containing two integers \( n \) and \( k \).

Output Format

A single line containing one integer, which is the answer.

Sample Input and Output

Sample Input #1

22 2

Sample Output #1

27

Sample Input #2

22 1

Sample Output #2

25

Notes

For \( 100\% \) of the data, \( 1 \le n \le 10^{18} \), \( 1 \le k \le 10^5 \).

见题面 Input 部分

见题面 Output 部分