NOVICE63  Special Numbers
Ted thinks that integers having equal number of 1's and 0's in their binary representation are special. Therefore, he wants to know how many such integers are present.
Note: For this problem, the binary representation of an integer(>0) is considered from the least significant bit to the last set bit. Which means, 5 has a binary representation of 101, 3 has a binary representation of 11 etc. As such, one example of a special number is 9 which has a binary representation, 1001.
Input
First line contains an integer T(atmost 100) denoting the total number of test cases. Each test case contains a single integer N(2 <= N <= 2^60). N is always a power of 2.
Output
A single integer denoting the total number of such special numbers in the range 1 to N (inclusive).
Example
Input: 3 8 16 32 Output: 1 4 4
hide comments
kshubham02:
20190309 13:30:17
"N is always a power of 2."  should post stuff like this in problem description, not in input section. I solved for general N on paper, then saw this. 

caro_linda2018:
20180704 23:11:45
In the second time 

vineetpratik:
20160706 21:47:56
very nice one :) you have to avoid overflow;


Liquid_Science:
20160211 13:43:52
Use long ,got 1 wa. 

priyank:
20150930 22:53:49
@ Shankar Chaudhary your output is wrong 

Jugal kishor sahu:
20150302 20:18:58
DP :) ans for 2,4,8 is 1. 

Rohan Jain:
20141207 20:08:45
take care of 2^58, 2^59, 2^60 case


Shankar Chaudhary:
20141008 15:40:28
for test cases check if am right @p_quantum


P_Quantum:
20140520 08:49:47
In one go..Easy!! 

govihuu:
20140209 20:10:12
I'm the 500TH solver :D Last edit: 20140218 03:32:23 
Added by:  amit karmakar 
Date:  20110702 
Time limit:  0.300s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem used in  http://www.spoj.pl/NOVICE6/ 