题目描述

有个变量 $i$ ，初始 $i=1$ 。

现在有两种操作：

1. $i=i+1$ ；
2. $i=i \times k$ 。

给定 $n,k$ ，对于所有可能的 $L$ ，问有多少种操作序列，满足操作 $2$ 的个数为 $L$ ，且依次执行所有操作后，$i \le n$ 。

输入格式

第一行一个整数 $k$ 。

第二行一个整数 $n$ 。

输出格式

对于所有可能的 $L$ ，按 $L$ 从小到大的顺序，每行输出一个答案。

样例

input

5
12

output

12
11

数据范围与提示

对于所有数据，$2 \le k \le 10$，$1 \le n \le k^{50}$。

• 子任务 $1$（$3$ 分）：$n \le 10^6$；
• 子任务 $2$（$10$ 分）：$k=2$，$n\le 10^9$；
• 子任务 $3$（$20$ 分）：$k=2$；
• 子任务 $4$（$20$ 分）：$n \le 10^9$；
• 子任务 $5$（$20$ 分）：$n \le 10^{18}$；
• 子任务 $6$（$27$ 分）：无特殊限制。