题目描述

给定一个正整数\(n\)，对于\(n\)的所有倍数（不为\(0\)），其二进制表示下\(1\)的个数的最小值是多少?
例如\(5\)的二进制表示为\(101\)，其中\(1\)的个数为\(2\)。

输入格式

共\(T\)行，第\(i\)行一个正整数，表示第\(i\)个询问的答案。

输出格式

输出到达第\(n\)阶花费的最少体力。

输入输出样例

输入

3
2
4
11

输出

1
1
2

样例解释

\(2\)的倍数：\(2\)二进制表示为\(10\)，\(1\)的个数为\(1\)个。
\(4\)的倍数：\(4\)二进制表示为\(100\)，\(1\)的个数为\(1\)个。
\(11\)的倍数：\(33\)二进制表示为\(100001\)，\(1\)的个数为\(2\)个。

数据范围

对于100%的数据，\(1\le n\le4\times10^6\)，\(1\le T\le3\)。
Subtask 1(30pts)：\(1\le n\le20\)。
Subtask 2(20pts)：\(1\le n\le1000\)。
Subtask 3(30pts)：\(1\le n\le10^5\)。
Subtask 4(20pts)：无特殊限制。

贡献者

题面，数据: 关怀大佬
核题: Ducati，b6e0