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: UNKNOWN_DIFFICULTY

Starter code:

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


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)


import math
try:
	t = int(input())
	while t > 0:
		n = int(input())
		c = 0
		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(c)
		t = t - 1
except:
	pass


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


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)


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)


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)


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


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)


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


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


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)