There are infinitely many coin denominations in the Byteland. They have values of 2ⁱ 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¹⁰⁰⁰.

Output

For each test case output minimal number of coins.

Example

Input:
5
507
29
8574
233
149
Output:
14
7
21
11
10