Yousef loves playing with functions in his free time. Today, he invents the following function:

Yousef will give you a list of queries, and you need to find the answers for them. For each query, you are given an integer n, and your task is to count the number of integers m in which (0 ≤ m ≤ n) and calc(n,  m) is an even number. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 105) specifying the number of test cases.

Each test case consists of a single line containing an integer n (0 ≤ n ≤ 1018), as described in the problem statement above.

Output

For each test case, print a single line containing the number of integers m in which (0 ≤ m ≤ n) and calc(n,  m) is an even number.

Example

Input

2
1
2

Output

0
1

题意：给你这么一个公式，然后给你一个n，让你求小于等于n的m使得calc(n,m)是偶数

把前几列列出来一看是杨辉三角

                  1                            偶数=0           奇数y=1           

              1       1                       偶数=0           奇数y=2

          1       2       1                  偶数=1           奇数y=2

     1      3         3        1            偶数=0           奇数y=4

1       4        6        4       1        偶数=3           奇数y=2

 

 思路：

多写几个就会发现，虽然偶数的个数没规律但是奇数的个数有规律

1 2 然后2 4    然后   2 4 4 8    然后   2 4 4 8 4 8 8 16    然后   2 4 4 8 4 8 8 16 4 8 8 16 8 16 16 32

合起来写就是

下标：0 1 2 3 4 5 6 7 8 9 10  11 12 13 14  15  16 17 18 19 20 21  22  23  24  25 26  27   28   29    30   31

个数：1 2 2 4 2 4 4 8 2 4   4   8   4   8   8   16   2   4   4   8   4   8   8   16    4   8    8   16    8    16    16    32

下标为偶数的时候，除以2个数不变

下标为奇数的时候，除以2个数减半

代码如下：

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll cal(ll n)
{
    ll sum=0;
    while(n)
    {
        if(n&1)sum++;
        n/=2;
    }
    return sum;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ll n;
        scanf("%lld",&n);
        ll ans=cal(n);
        printf("%lld\n",n+1-((ll)1<<ans));
    }
	return 0;
}

 不过做题的时候想到的是一种麻烦的思路

具体是什么就不说了，光上代码吧，（自闭中）

#include<cstdio>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll; 
ll dfs(ll n,int temp)
{
    if(n==1||n==2||n==3)
    {
        if(n==1)
            n*=2;
        else
            n=(n-1)*2;
        if(temp==0)
            return n;
        else if(temp==1)
            return n*2;
        else if(temp==2)
            return n*2;
        else if(temp==3)
            return n*4;
    }
    temp++;
    if(n%4==0)
        return dfs(n/4,0)*((ll)pow(2,temp/2));
    else if(n%4==1)
        return dfs(n-1,1)*((ll)pow(2,temp/2));
    else if(n%4==2)
        return dfs(n-2,2)*((ll)pow(2,temp/2));
    else if(n%4==3)
        return dfs(n-3,3)*((ll)pow(2,temp/2));
}
int main(){ 
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ll n,ans;
        scanf("%lld",&n);
        if(n==0||n==1)
        {
            printf("0\n");
            continue;
        }
        if(n==2)
        {
            printf("1\n");
            continue;
        }
        if(n==3)
        {
            printf("0\n");
            continue;
        }
        if(n%4==0)
            ans=dfs(n/4,0);
        else if(n%4==1)
            ans=dfs(n-1,1);
        else if(n%4==2)
            ans=dfs(n-2,2);
        else if(n%4==3)
            ans=dfs(n-3,3);
        printf("%lld\n",n-ans+1);
    } 
	return 0;
}