给定一个长度为 $n$ 的数列，请你求出数列中每个数的二进制表示中 $1$ 的个数。

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个整数，表示整个数列。

输出格式

共一行，包含 $n$ 个整数，其中的第 $i$ 个数表示数列中的第 $i$ 个数的二进制表示中 $1$ 的个数。

数据范围

$1 \le n \le 100000$,
$0 \le 数列中元素的值 \le 10^9$

输入样例：

5
1 2 3 4 5

输出样例：

1 1 2 1 2

样例：基础正确性。

全 0（10 个）：卡把 0 的 popcount 写成 1、或循环条件 while(x) 忘记输出 0。

n=1 且值=0：最小规模 + 0 边界；卡初始化/输出格式错误。

n=1 且值=1e9：单点大数；卡溢出/类型不够（尤其用 short/int16 等）。

全部是 2 的幂（2^0..2^29）：每个答案都应为 1；卡把位运算写错、或误把十进制当二进制处理。

全部是 (2^k-1)（1..30 位全 1）：答案应递增；卡只统计到固定 32 位/位数上限写错、或移位终止条件写错。

交替位模式（715827882, 357913941）：卡按“十进制数字”数 1、或字符串转二进制时处理错误（交替位对位运算很敏感）。

小范围随机（0..1000，20 个）：综合正确性；卡某些分支 bug（比如 x&1 / x>>=1 写反）。

大量重复值（7/8/9 混合）：卡缓存/复用错误、或输出位置错位（重复更容易看出来）。

0..63 递增：低位变化密集；卡位移/掩码写错、或把 >> 写成 <<。

2^k 附近（31,32,33…）：卡进位边界；比如把 while(x>1)、或漏算最高位。

接近 1e9 的大数（999999937 等）：卡大数处理、以及某些“按位循环到 2^30”边界问题。

混合：0、1..5、1e9-1、1e9：卡 0 + 大数一起出现时的逻辑分支问题。

中等规模随机（100 个，0..1e9）：综合正确性 + 一点性能；卡只会处理小数/没覆盖到高位。

n=100000 超大随机（值都限制到 ≤1e9）：强压力；卡 O(n * 位数) 还好，但卡更慢的做法（如每个数转字符串二进制、或错误的 O(n^2)）。

100..0 递减：卡输出顺序/读入顺序错误（比如排序后再算、或读错）。

回文序列（0..49..0）：卡输出错位/漏输出一个/多输出一个（结构对称，容易看出不对）。

500 个相同的大幂（2^29）：答案全 1；卡重复大数时的性能/缓存 bug。

很多 0 夹杂小数（0,1,1,0,2,0,3...）：卡对 0 的处理 + 输出空格格式（中间有很多 0）。

位很“满”的数（1000000000, 2^29-1, 2^28-1）：卡高位密集 1 的统计；同时第一项是 1e9（不是全 1），卡“以为越大 1 越多”的错误直觉写法。

3 的倍数序列（3,6,9,...,300）：卡某些基于奇偶/最低位的错误优化（只看奇偶会错）。

200 个里 70% 是 0 的随机混合：卡大量 0 时的分支/性能/输出（尤其错误地跳过 0）。

单个高位 1（不同位位置：0,5,10,...,29）：答案都应为 1；卡移位次数/位宽假设错误。

8 的倍数（8,16,24,...,64）：低 3 位全 0；卡统计时把低位当作循环终止条件（如 while(x%2==0) break 之类的怪写法）。

n=100000 全是 (2^29-1)：强压力 + 高 popcount（答案全 29）；卡慢实现（转二进制字符串/逐位拼接）、以及输出性能（没用快 IO 可能 TLE）。