N-interesting Numbers

Time limit5sMemory limit512 MB

Summary

Given N and n, find the n-th largest number X whose largest prime factor p is at most 127 and satisfies p^k at most N, where k counts the prime factors.

Level: Medium7 of 10
Topics: Backtracking, Number theory, Sorting
Solved: No attempts yet

Statement

An integer $X \ge 2$ is called $N$ -interesting if, in its prime factorization $X=p_1p_2\cdots p_k$ , the largest factor $p_i$ satisfies $p_i^k \le N$ and $p_i \le 127$ .

You are given two integers $N$ and $n$ . It is guaranteed that at least $n$ $N$ -interesting numbers exist and that there are finitely many of them. Find the $n$ -th largest $N$ -interesting number.

Input

The first line contains two integers $N$ and $n$ ( $2 \le N \le 10^{18}$ ; $1 \le n \le 8 \cdot 10^5$ ).

Output

Print one integer: the $n$ -th largest $N$ -interesting number.

Examples1

Example 1
Input
```
3110 21
```
Expected output
```
1573
```