"To succeed, jump as quickly at oppurtunities as you do at conclusions - Franklin"

X is a follower of Franklin and he has taken this quote too seriously.
Now whenever he has to go from a place to another, he does this by jumping instead of walking.
He takes jumps such that the distance covered in one jump can be expressed as a power of 2.

More formally,
if X covers a distance of y in one jump then y=2^m for some m>=0.
Now he is wondering what minimum number of jumps he has to take to cover a distance of N.
Help him.

Input :

First line will contain an integer T (number of testcases).
Each of the next T lines contain an integer N.

Output :

For each N print the required answer on a new line.

Constraints :

T<=10^5
N<=10^18