DugDug has an infinite coin supply of denomination 1,2,4,8,16,32,.. upto 2^64.He was challenged by his friend TukTuk.
TukTuk wants DugDug to collect n units of money using minimum coins using above given coins supply. As DugDug is busy in doing some
work. Help him to collect the money using minimum number of coins.

Input

First line contains T . no of test cases

next t lines contains n

Output

minimum no of coins used to make n

Constraint

0 < T < 100

0 ≤ n ≤ 10^10

SAMPLE INPUT
2
2
7

SAMPLE OUTPUT
1
3

Explanation

for making 2 we can use 1 coin of denomination 1

for making 7 we can use 1 coin of 4 , one of 2 and 1 of 1

见题面

见题面