Description

If a positive integer $M > 1$ has $k$ terms in its prime factorization, its largest prime factor is $a_k$, and it satisfies $a_k^k \le N$, $a_k < 128$, then $M$ is called an $N$-pseudo-smooth number.

Given $N$, among all integers, find the $K$-th largest $N$-pseudo-smooth number.

Clarification: Let $M = 36 = 2^2 \times 3^2$. Then the corresponding $k = 4$. That is, by the Fundamental Theorem of Arithmetic, write $M = \prod_{i=1}^n p_i^{c_i}$ and $k = \sum_{i=1}^n c_i$. “$K$-th largest” is literal: the $K$-th from largest to smallest.

Modified by expect2004 on 2020-11-25; this may be his last contribution to the Luogu public problem set before retirement.

Input Format

One line with two space-separated integers $N$ and $K$.

Output Format

One line containing a single integer, the answer.

12345 20

9167

Hint

For $30\%$ of the testdata, $N \le 10^6$.
For $100\%$ of the testdata, $2 \le N \le 10^{18}, 1 \le K \le 800000$. It is guaranteed that there are at least $K$ numbers that satisfy the requirements.

Translated by ChatGPT 5