## 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 (at most 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```

## Code Examples

### #1 Code Example with Python Programming

```Code - Python Programming```

``````def f(n, k):
return fac[n] // fac[k] // fac[n - k]
fac = [1] * 123
for i in range(1, 123):
fac[i] = fac[i - 1] * i
T = int(input())
for _ in range(T):
N = int(input())
if N == 2:
print(1)
continue
for i in range(65):
if N & (1 << i):
N = i
break
result = 0
for j in range(1, N // 2 + 1):
result += f(j + j - 1, j)
print(result)``````
Copy The Code &

Input

cmd
3
8
16
32

Output

cmd
1
4
4

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <cassert>
#include <iostream>
using namespace std;

const int MAX = 1000005;
int phi[MAX];

int main()
{
for(int i=1; i<=MAX; i++)
phi[i]=i;

for(int i=2; i<=MAX; i++)
{	if(phi[i]==i)
{	// This condition guarantees that i is prime since it was not modified by any number <i.
for(int j=i; j<=MAX; j+=i)
phi[j]-=(phi[j]/i);		// In this step we multiply (1-1/i) to each multiple of i, since it would be a prime factor in factorisation of all its multiples.
}
}

cin.tie(nullptr);
ios_base::sync_with_stdio(false);

int t;
cin>>t;
while(t--)
{   int p;
cin >> p;
assert(1<=p && p<=1000000);
cout << phi[phi[p]]<<'\n';
}
}``````
Copy The Code &

Input

cmd
3
8
16
32

Output

cmd
1
4
4