For a positive integer $k$, a magic number $x$ is defined as a positive integer such that the decimal representation of $x \times (10^k - 1)$ does not contain the digit $9$. You need to find the $n$-th magic number.
Input
A single line containing two integers $k$ and $n$.
Output
A single line containing the $n$-th magic number.
Examples
Input 1
1 8
Output 1
9
Input 2
5 84
Output 2
11235
Constraints
| Test Cases | $k$ | $n \le$ |
|---|---|---|
| $1 \sim 2$ | $\le 3$ | $1000$ |
| $3 \sim 6$ | $\le 4$ | $10^{18}$ |
| $7 \sim 10$ | $> 4$ |
For all test cases, $1 \le k \le 18$, $1 \le n \le 10^{18}$.