問題文


個の整数 進数表記で与えられます。各 () について,その値を 進数表記したときに立っているビット数を答えよ.

制約


  • 入力はすべて整数

注意


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

入力


N
A_1
:
A_N

出力


行出力せよ. 行目には, 進数表記したときに立っているビット数を 進数表記で答えよ.最後に改行を入れること.

入出力例


入力例1


4
0
1
3
5

出力例1


0
1
2
2

各整数を 進数で表すと,次のようになります.

入力例2


5
3366131626
936937807
4155860106
1540076410
1578502508

出力例2


15
17
18
20
14

たとえば, です.

Submit


Go (1.14)