题目描述
对于正整数 $k$，定义魔法数 $x$ 满足 $x\times(10^k-1)$ 的十进制表示不包含 $9$ 的正整数，你需要求出第 $n$ 个魔法数。
输入格式
一行两个整数 $k, n$。
输出格式
一行一个整数表示第 $n$ 个魔法数。
样例
1 8
9
5 84
11235
数据范围与提示
| 测试点编号 | $k$ | $n\leq$ |
|---|---|---|
| $1\sim 2$ | $\leq 3$ | $1000$ |
| $3\sim 6$ | $\leq 4$ | $10^{18}$ |
| $7\sim 10$ | $\gt 4$ |
对于所有数据，$1\leq k\leq {18}$，$1\leq n\leq 10^{18}$。
时间限制：$2\texttt{s}$
空间限制：$512\texttt{MB}$