popcount

問題文

$N$ 個の整数 $A_1, \ldots, A_N$ が $10$ 進数表記で与えられます。各 $A_i$ ($1 \le i \le N$) について，その値を $2$ 進数表記したときに立っているビット数を答えよ．

制約

• $1 \le N \le 10^5$
• $0 \le A_i < 2^{64}$
• 入力はすべて整数

注意

実行時間制限が厳しめであるため，特に Python を使用する場合は注意すること．

入力

N
A_1
:
A_N

出力

$N$ 行出力せよ．$i$ 行目には，$A_i$ を $2$ 進数表記したときに立っているビット数を $10$ 進数表記で答えよ．最後に改行を入れること．

入出力例

入力例1

4
0
1
3
5

出力例1

0
1
2
2

各整数を $2$ 進数で表すと，次のようになります．

• $0_{(10)} = 0_{(2)}$
• $1_{(10)} = 1_{(2)}$
• $3_{(10)} = {11}_{(2)}$
• $5_{(10)} = {101}_{(2)}$

入力例2

5
3366131626
936937807
4155860106
1540076410
1578502508

出力例2

15
17
18
20
14

たとえば， ${3366131626}_{(10)} = {11001000101000110001011110101010}_{(2)}$ です．