Codeforces Round #516 (Div. 2, by Moscow Team Olympiad) B. Equations of Mathematical Magic

B. Equations of Mathematical Magic

 

Colossal! — exclaimed Hawk-nose. — A programmer! That's exactly what we are looking for.

Arkadi and Boris Strugatsky. Monday starts on Saturday

Reading the book "Equations of Mathematical Magic" Roman Oira-Oira and Cristobal Junta found an interesting equation: a−(a⊕x)−x=0a−(a⊕x)−x=0 for some given aa, where ⊕⊕ stands for a bitwise exclusive or (XOR) of two integers (this operation is denoted as ^ or xor in many modern programming languages). Oira-Oira quickly found some xx, which is the solution of the equation, but Cristobal Junta decided that Oira-Oira's result is not interesting enough, so he asked his colleague how many non-negative solutions of this equation exist. This task turned out to be too difficult for Oira-Oira, so he asks you to help.

Input

Each test contains several possible values of aa and your task is to find the number of equation's solution for each of them. The first line contains an integer tt (1≤t≤10001≤t≤1000) — the number of these values.

The following tt lines contain the values of parameter aa, each value is an integer from 00 to 230−1230−1 inclusive.

Output

For each value of aa print exactly one integer — the number of non-negative solutions of the equation for the given value of the parameter. Print answers in the same order as values of aa appear in the input.

One can show that the number of solutions is always finite.

Example

input

Copy

3
0
2
1073741823

output

Copy

1
2
1073741824

题意：求出a-(a^x)-x=0解的个数。

思路：既然是按位异或当然就要认真推规律了。

1. 首先很明显发现，0和a必然是解，所以最小的解就是0，接着我们观察这个式子，a-a^x-x=0。

2. a是给定非负整数，所求x也是非负整数（题目要求），a异或一个数，只有两种情况，要么<=a，要么>a。

    先看变大的情况，如果a^x变得比原来的a大了，a-a^x必然负数，x非负整数，负数减非负整数：a-a^x-x<0必然无解。

    由此推理，可得解的范围[0~a]，闭区间。

3. 接下来，就是想办法让a变小了，由此想到二进制，比如10->1010，我们只要把1变成0就可以变小。

    仔细看a=a^x+x（移项而已），总结算式：a异或一个数加上它又变回a了

   1010  ^10  =1000    1000+10 =1010；

   1010  ^11  =1001    1001+11 !=1010；

   显然第二个虽然变小了，但不是解，所以最终规律，就是将1变没的方案数，对于一个1有两种选择，那么n个1，2^n；

  最后一个特判，当a的二进制全是1时，比如7，此时输出a+1，当a是0，输出1。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a,ans,ok;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&a);
        if(a==0){printf("1\n");continue;}
        int a1=a;
        ans=0;
        ok=0;
        while(a1)
        {
            if(a1%2==0)ok=1;   //此时不全是1
            if(a1%2==1)ans++;   //1的个数
            a1/=2;
        }
        if(ok==0)printf("%d\n",a+1);
        else printf("%d\n",1<<ans);
    }
    return 0;
}