NOVICE63 - Special Numbers

no tags 

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: 2019-03-09 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: 2018-07-04 23:11:45

In the second time

vineetpratik: 2016-07-06 21:47:56

very nice one :) you have to avoid overflow;
DP,map,pre-computation and then AC in 0.0 sec

Liquid_Science: 2016-02-11 13:43:52

Use long ,got 1 wa.

priyank: 2015-09-30 22:53:49

@ Shankar Chaudhary your output is wrong

Jugal kishor sahu: 2015-03-02 20:18:58

DP :) ans for 2,4,8 is 1.

Rohan Jain: 2014-12-07 20:08:45

take care of 2^58, 2^59, 2^60 case
o/p for 2 should be 1 :D (made a silly mistake)

Shankar Chaudhary: 2014-10-08 15:40:28

for test cases check if am right @p_quantum
2
64
256
1024
answer is
1
9
16
25

Last edit: 2014-10-08 15:41:09
P_Quantum: 2014-05-20 08:49:47

In one go..Easy!!

govihuu: 2014-02-09 20:10:12

I'm the 500TH solver :D

Last edit: 2014-02-18 03:32:23

Added by:amit karmakar
Date:2011-07-02
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/