PAYING - Paying in Byteland

There are infinitely many coin denominations in the Byteland. They have values of 2i 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 ≤ 101000.

Output

For each test case output minimal number of coins.

Example

Input:
5
507
29
8574
233
149

Output:
14
7
21
11
10

Added by:gawry
Date:2004-07-07
Time limit:5.923s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2019-07-25 22:01:45
This was fun to crack =)
2016-01-19 19:59:54 lotus_guy
loved it :D
2015-07-01 02:55:16 apopa
@Adit Goel
{1,1,1,2,3,4,7,15,31,63,126,253} is not a valid solution for 507 because 3, 7, 15, 31, 63, 126, and 253 are not valid coin denominations; this can be inferred from the problem statement.
2015-02-23 18:51:50 Adit Goel
why is the answer for 507->14
{1,1,1,2,3,4,7,15,31,63,126,253}
makes all possible sums
2014-11-20 00:17:20 Daniel Ospina Acero
Any problem that anyone might be facing, if the test cases are working fine, has to do with large numbers.
2014-02-06 13:26:39 nikhil


Last edit: 2014-02-06 16:54:13
2013-05-31 16:06:22 Nitesh Lulla
is limit of n actually 10^1000. will we have to store the number in strings?
2011-11-12 13:15:24 Aamir Khan
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 ?

Please read the problem statement carefully .. the sum of the values of the coins you're using must be equal to 29 !

Last edit: 2011-11-16 09:01:00
2011-07-22 05:24:34 Arun prasath
i want answer for this , wher can i find the code???
2011-05-14 12:05:55 Radhika
can someone provide me more test cases..?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.