题目描述

给定n个数字，依次输出每个数字二进制中1的个数。

输入格式

第一行输入一个数N；

之后N行，每行输入一个数a[i]。

输出格式

输出N行，每行一个数每个数字二进制包含1的个数。

样例数据

input

3

15

1

22

output

4

1

3

数据规模与约定

对于100%的数据，2≤N≤200000，1≤a[i]≤10^18；

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$