题目描述

给定一个长度为 $n$ 的数列，数列中的每个元素都是一个整数。对于数列中的每一个数，我们需要求出它的二进制表示中 $1$ 的个数，并将这些个数输出。

输入格式

输入的第一行是一个整数 $n$（$1 \le n\le10^6$），表示数列的长度。

输入的第二行包含 $n$ 个整数 $a_i$（$0 \le a_i\le10^9$），每个整数之间用空格分隔。

输出格式

输出一行，包含 $n$个整数，第 $i$ 个整数表示数列中第 $i$ 个数的二进制表示中 $1$ 的个数。整数之间用空格分隔。

样例

5   
4 8 15 16 23

1 1 4 1 4

提示

样例1解释

• 第一个数 $4$ 的二进制表示为 $100$，其中 $1$ 的个数为 $1$。
• 第二个数 $8$ 的二进制表示为 $1000$，其中 $1$ 的个数为 $1$。
• 第三个数 $15$ 的二进制表示为 $1111$，其中 $1$ 的个数为 $4$。
• 第四个数 $16$ 的二进制表示为 $10000$，其中 $1$ 的个数为 $1$。
• 第五个数 $23$ 的二进制表示为 $10111$，其中 $1$ 的个数为 $4$。

数据范围

• 测试点 $1 - 10$ 满足 $1 \le n\le10^3$，$0 \le a_i\le10^6$。
• 测试点 $11 - 20$ 满足 $1 \le n\le10^5$，$0 \le a_i\le10^9$。
• 测试点 $21 - 25$ 满足 $1 \le n\le10^6$，$0 \le a_i\le10^9$。