There is a variable $i$, initially $i=1$.

There are two types of operations:

1. $i=i+1$;
2. $i=i \times k$.

Given $n$ and $k$, for all possible values of $L$, find the number of operation sequences such that the number of type 2 operations is exactly $L$, and after performing all operations, $i \le n$.

Input

The first line contains an integer $k$.

The second line contains an integer $n$.

Output

For all possible values of $L$, output the answer for each $L$ in increasing order, one per line.

Examples

Input 1

5
12

Output 1

12
11

Subtasks

For all data, $2 \le k \le 10$ and $1 \le n \le k^{50}$.

• Subtask 1 (3 points): $n \le 10^6$;
• Subtask 2 (10 points): $k=2$, $n \le 10^9$;
• Subtask 3 (20 points): $k=2$;
• Subtask 4 (20 points): $n \le 10^9$;
• Subtask 5 (20 points): $n \le 10^{18}$;
• Subtask 6 (27 points): No additional constraints.