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 ≤ 10^5) specifying the number of test cases.

Each test case consists of a single line containing an integer n (0 ≤ n ≤ 10^18), 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

分析一下这个函数，发现其实就是组合数的递推公式
问有多少个m(0<=m<=n)使得calc（n,m）是偶数，其实也就是杨辉三角第（n+1）行中偶数的个数
打个表找规律发现偶数规律好难找(╥╯^╰╥)，那就换个角度找奇数的规律


2是1的2倍
2,4是1,2的2倍
2,4,4,8是1,2,2,4的2倍
……
a[0]=1
a[n]=a[n-x]*2 (x是小于等于n的最大的那个2的次幂，也就是2进制中最高位上那个1对应的数）
即2进制中有几个1，奇数个数就是2的几次方
最后用n+1-奇数个数就是偶数个数了（杨辉三角中n对应第n+1行，有n+1个数）

#include<cstdio>
using namespace std;
int main(){
	int T;
	long long n;
	scanf("%d",&T);
	while(T--){
		scanf("%I64d",&n);
		long long m=n;
		int cnt=0;//2进制中1的个数 
// while(m) //这种也行
// {
// if(m&1) cnt++;
// m>>=1; 
// }
		while(m)        //如果要记忆化搜索的话只能用这种
		{   
			cnt++;
			m-=m&(-m);
		}
		long long ans=1ll<<cnt;//奇数的个数 （long long 1) 
		printf("%I64d\n",n+1-ans);//偶数的个数 
	}
	return 0; 
}