BINREP - Binary representation

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

Added by:kousik
Date:2013-08-30
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP D JAVA PYTHON PYTHON3 PY_NBC RUBY
Resource:Own

hide comments
2018-05-27 12:55:59
Those getting 50 in Python, read the statement carefully.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.