题目描述

输入一个整数 $n(1 \le n \le 2 \cdot 10^9)$，依次统计 $1 \sim n$ 范围内：

• 二进制表示中恰好 $1$ 位为 $1$ 的数的个数；
• 二进制表示中恰好 $2$ 位为 $1$ 的数的个数；
• 二进制表示中恰好 $3$ 位为 $1$ 的数的个数；
• ……

输入格式

一个整数 $n(1 \le n \le 2 \cdot 10^9)$。

输出格式

输出若干行，每行包含一个整数。其中第 $i$ 行的整数表示 $\le n$ 的正整数中存在多少个数的二进制表示中恰好存在 $i$ 位为 $1$。

输出的行数等于 $1 \sim n$ 中二进制中 $1$ 位数最多的那个数对应的 $1$ 的位数。

样例

100

7
21
33
26
11
2

12345678

24
275
2002
10395
40964
127278
319722
660493
1135222
1635710
1984546
2030909
1751707
1269288
768043
384527
157165
51442
13112
2495
331
27
1

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 2 \cdot 10^6$
• 对于 $100\%$ 的数据，$1 \le n \le 2 \cdot 10^9$