二进制 1 的个数

题目描述

给定 q 个非负整数。对于每个整数 x，请输出它的二进制表示中 1 的个数。

例如：13 的二进制为 1101，其中有 3 个 1。

输入格式

第一行一个整数 q。

接下来 q 行，每行一个非负整数 x。

输出格式

输出 q 行，每行一个整数，表示对应 x 的二进制中 1 的个数。

样例

输入

4
0
13
44
2026

输出

0
3
3
8

数据范围

• 1 <= q <= 2 * 10^5
• 0 <= x <= 10^18

提示

除了逐位判断之外，也可以思考：x & (x - 1) 会对 x 的二进制产生什么变化？