Motu and Patlu are playing with a Magical Ball. Patlu find some interesting pattern in the motion of the ball that ball always bounce back from the ground after travelling a linear distance whose value is some power of $2$. Patlu gave Motu total distance $D$ travelled by the ball and ask him to calculate the minimum number of bounces that the ball makes before coming to rest.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, single integers $D$.
- Note : Power of $2$ must be a non-negative integer. 

-----Output:-----
For each testcase, output in a single line answer, the minimum number of bounces the ball makes before coming to rest.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1$ $\leq$ $M$< $10$^18

-----Sample Input:-----
1
13 

-----Sample Output:-----
2

-----EXPLANATION:-----

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
test=int(input())
for _ in range(test):
    n=int(input())
    n=list(bin(n))
    ans=n.count('1')
    print(ans-1)

# cook your dish here
t=int(input())
for i in range(t):
    n=int(input())
    binary=bin(n)
    setb=[ones for ones in binary[2:] if ones=='1']
    print(len(setb)-1)


# cook your dish here
import math
try:
    
    t=int(input())

    while(t>0):
        n=int(input())
        c=0
        '''while(n>=1):
            if(n%2==1):
                c=c+1
            n=n//2'''
        m=n
        s=0
        if(math.log2(n)-int(math.log2(n))==0):
            print(0)
        else:
            while(n>=2):
                if(bool(math.log2(n))):
                    c=c+1
                r=2**(int(math.log2(n)))
                s=s+r 
                n=n-r
               
                if(s==m):
                    c=c-1
        #print(n)
            print(c)
        t=t-1
except:
    pass

test=int(input())
for _ in range(test):
    n=int(input())
    n=list(bin(n))
    ans=n.count('1')
    print(ans-1)

# cook your dish here
import math;
count = 0;

def steps(num):
    nonlocal count;
    
    expo=int(math.log(num,2));
    nearPow=int(pow(2,expo));
    if(nearPow==num):
        return count;
    num-=nearPow;
    count+=1;
    if(num==1):
        return count;
    else:
        steps(num);
    return count;

    
iterator=int(input());
while(iterator>0):
    count=0;
    num=int(input());
    print((steps(abs(num))));
    iterator-=1;


try:
    t = int(input())
    for _ in range(t):
        N = int(input())
        a = bin(N)

        print(a.count('1') -1 )

except:
    pass

# cook your dish here
import math
t=int(input())
for i in range(t):
    k=int(input())
    count=0
    temp=(int(math.log2(k)))
    for j in range(temp,-1,-1):
        if((k-(2**j))>=0):
            k=k-(2**j)
            
            count=count+1
    print(count-1)


def countBits(n):
	count=0
	while n>0:
		n = n &n-1
		count+=1
	return count	

t = int(input())
for _ in range(t):
	n = int(input())
	print(countBits(n)-1)

# cook your dish here
def balls():
    d=int(input())
    i=0
    while(1):
        if (2**i)>d:
            i-=1 
            break
        i+=1 
    temp=0
    result=0
    j=i 
    while(j>=0):
        if (temp+(2**j))==d:
            return result
        if (temp+(2**j))>d:
            j-=1 
        else:
            temp+=(2**j)
            result+=1
    return result
t=int(input())
for loop in range(t):
    print(balls())

for i in range(int(input())):
           a=int(input())
           sum=0
           x=2
           while (a//x)!=0:
               sum+=1
               x*=2
          
           temp=0
           while a>=0 and sum>=0:
             if 2**sum<=a:
               a-=(2**sum)
               temp+=1
             sum -= 1

           print(temp-1)


for i in range(int(input())):
           a=int(input())
           sum=0
           x=2
           while (a//x)!=0:
               sum+=1
               x*=2
          
           temp=0
           while a>=0 and sum>=0:
             if 2**sum<=a:
               a-=(2**sum)
               temp+=1
             sum -= 1

           print(temp-1)


import math as m
for _ in range(int(input())):
    d=int(input())
    p=d
    c=0
    while(True):
        a=int(m.log2(d))
        c=c+1
        d=d-2**a
        if d==1 or d==0:
            if p%2==0:
                c=c-1
                print(c)
                break
            else:
                print(c)
                break

import math
T=int(input())
for _ in range(T):
    D=int(input())
    count=0
    while D>0:
        p = int(math.log(D, 2))
        D = D - 2**p
        count+=1
    print(count-1)

# cook your dish here
import math
t=int(input())
for _ in range(t):
    n=int(input())
    if math.ceil(math.log2(n))== math.floor(math.log2(n)):
        print(0)
    else:
        x,c=0,0
        while n>0:
            x=2**math.floor(math.log2(n))
            c+=1
            n=n-x
            if math.ceil(math.log2(n))== math.floor(math.log2(n)):
                break
        print(c)    


import math
t = int(input())
while(t!=0):
    d = int(input())
    bounce=0
    while(d>0):
        p = int(math.log(d,2))
        d = d- (pow(2,p))
        if(d!=0):
            bounce+=1;
    print(int(bounce))
    t-=1

# cook your dish here
def ConDecBin(num, count):
	count += num%2
	if num > 1:
		ConDecBin(num//2, count)
	else:
		print(count - 1)

for k in range(int(input())):
	num = int(input())
	count = 0

	ConDecBin(num, count)

# def b(n):
#     str=""
#     if n>1:
#         b(n//2)
#     print(n%2,end="")
t=int(input())
for i in range(t):
    n=int(input())
    # b(n)
    binary=bin(n)
    setBits=[ones for ones in binary[2:] if ones=='1']
    print(len(setBits)-1)


try:
     t=int(input())
     for i in range(t):
          d=int(input())
          li=list(bin(d))
          print(li.count('1')-1)
except:
     pass


# cook your dish here
import numpy as np

def bb(d):
    if(d==0):
        return 0
    elif(d==1 or d==2):
        return 1
    else:
        return 1+bb(d-2**int(np.log2(d)))


T = int(input())
tests = np.zeros(T)
for i in range(T):
    tests[i] = int(input())
    print(bb(tests[i])-1)

def bitsoncount(x):
    return bin(x).count('1')
for t in range(int(input())):
    x = int(input())
    if x == 0:
        print(0)
    else:

        print(bitsoncount(x)-1)

for _ in range(int(input())):
    a=int(input())
    b=list(bin(a))
    print(b.count('1')-1)


t=int(input())
while(t!=0):
    k=0
    n=int(input())
    if n&n-1==0:
        print(0)
    else:
        while(n!=0):
             n=n&n-1
             k+=1
        print(k-1)
    t-=1




t=int(input())
while(t!=0):
    k=0
    n=int(input())
    if n==1:
      print(0)
    elif n&n-1==0:
        print(0)
    else:
        while(n!=0):
             n=n&n-1
             k+=1
        print(k-1)
    t-=1




import math
for _ in range(int(input())):
    d=int(input())
    c=0
    while d>0:
        n=math.floor(math.log2(d))
        x=pow(2,n)
        d-=x
        c+=1
    print(c-1)

for _ in range(int(input())):
    d=int(input())
    print(str(bin(d)).count("1")-1)