Description

Orange本周末刚刚从成都回来，以至于他现在满脑子都是0和1，现在，他将给定你一个数 $x$，请你求出 $x$ 的二进制表示中有多少个1。

Format

Input

输入包含多组测试数据，第一行为测试数据组数 $T(1 \le T \le 10^5)$。

对于每组测试数据，输入包含一个整数 $x(0 \le x \le 10^{18})$，表示一次询问。

Output

对于每组询问，输入一个整数表示答案。

Samples

5
1
2
3
4
5

1
1
2
1
2