Question statement

Now we represent a natural number N by the maximum numbers that are less than or equal to N in Fibonacci sequence: N = b1*A1 + b2*A2 + …

Hence N can be represented as: bnbn-1…b1. For eg, 1 = 1f, 2 = 10f, etc.

On writing all N successively in Fibonacci system, we will obtain a sequence like this: 110… We call this “Fibonacci sequence till N in bit format”.

Input

T, the number of test cases, followed by T lines.

Each line containing the positive integer M, where 0<=M<=1018

Output

T lines of output, each line contain the positive integer, denoting the count of the numbers of times that bit 1 appears in first M bits of this sequence.

How to utilise fibonacci to solve this problem.