시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 (추가 시간 없음) 512 MB411100.000%

문제

Целое число $X \ge 2$ считается $N$-интересным, если в его разложении на простые множители $X=p_1p_2\cdots{}p_k$ наибольший из множителей $p_i$ удовлетворяет условиям $p_i^k \le N$ и $p_i \le 127$.

Даны два целых числа $N$ и $n$. Гарантируется, что $N$-интересных чисел существует не менее $n$, и при этом их конечное число.

Найдите $n$-е по убыванию $N$-интересное число.

입력

Первая строка входных данных содержит два целых числа $N$ и $n$ ($2 \le N \le 10^{18}$; $1 \le n \le 8 \cdot 10^5$).

출력

Выведите одно целое число --- $n$-е по убыванию $N$-интересное число.

예제 입력 1

3110 21

예제 출력 1

1573