PAYING - Paying in Byteland

no tags 

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

hide comments
nadstratosfer: 2019-07-25 22:01:45

This was fun to crack =)

lotus_guy: 2016-01-19 19:59:54

loved it :D

apopa: 2015-07-01 02:55:16

@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.

Adit Goel: 2015-02-23 18:51:50

why is the answer for 507->14
{1,1,1,2,3,4,7,15,31,63,126,253}
makes all possible sums

Daniel Ospina Acero: 2014-11-20 00:17:20

Any problem that anyone might be facing, if the test cases are working fine, has to do with large numbers.

nikhil: 2014-02-06 13:26:39

Last edit: 2014-02-06 16:54:13
Nitesh Lulla: 2013-05-31 16:06:22

is limit of n actually 10^1000. will we have to store the number in strings?

Aamir Khan: 2011-11-12 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 ?

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
Arun prasath: 2011-07-22 05:24:34

i want answer for this , wher can i find the code???

Radhika: 2011-05-14 12:05:55

can someone provide me more test cases..?


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