SP9103 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.

First line contains an integer T(atmost 100) denoting the total number of test cases. Each test case contains a single integer N(2

A single integer denoting the total number of such special numbers in the range 1 to N (inclusive).