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.