Here's an easy and direct question. Find the number of 1's in the binary representation of a number N such that N <= 10^9.

Input

The first line contains the number of test cases t (0 <= t <= 100), followed by the numbers. Each number can be (-10^9 <= N <= 10^9). Use unsigned long as your data type.

Output

The number of 1's in binary representation of each number.

Example

Input:
5
3
12
7
9
5

Output:
2
2
3
2
2