PAYING  Paying in Byteland
There are infinitely many coin denominations in the Byteland. They have values of 2^i for i=0,1,2,... . We will say that set of coins c1,c2,...,ck is perfect when it is possible to pay every amount of money between 0 and c1+...+ck using some of them (so {4,2,2,1} is perfect while {8,1} is not). The question is  is it always possible to change given sum n into a perfect set of coins? Of course it is possible ;). Your task will be more complicated: for a sum n you should find minimal number of coins in its perfect representation.
Input
First line of input contains one integer c<=50  number of test cases. Then c lines follow, each of them consisting of exactly one integer n<=10^1000.
Output
For each test case output minimal number of coins.
Example
Input: 5 507 29 8574 233 149 Output: 14 7 21 11 10
hide comments
lotus_guy:
20160119 19:59:54
loved it :D


apopa:
20150701 02:55:16
@Adit Goel


Adit Goel:
20150223 18:51:50
why is the answer for 507>14


Daniel Ospina Acero:
20141120 00:17:20
Any problem that anyone might be facing, if the test cases are working fine, has to do with large numbers. 

nikhil:
20140206 13:26:39
Last edit: 20140206 16:54:13 

Nitesh Lulla:
20130531 16:06:22
is limit of n actually 10^1000. will we have to store the number in strings? 

Aamir Khan:
20111112 13:15:24
To get the all values <=29 : I can take the coins of 1,2,4,8,16 and make all possible sum. Why the answer is 7 for this test case ?


Arun prasath:
20110722 05:24:34
i want answer for this , wher can i find the code??? 

Radhika:
20110514 12:05:55
can someone provide me more test cases..? 
Added by:  gawry 
Date:  20040707 
Time limit:  5.923s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 