#include <bits/stdc++.h>
using namespace std;
struct point {
  long double x, y;
  point() {
    x = 0;
    y = 0;
  }
  point(long long a, long long b) {
    x = a;
    y = b;
  }
  bool operator==(const point &b) { return x == b.x and y == b.y; }
  bool operator>(const point &b) {
    if (x > b.x) return true;
    if (x < b.x) return false;
    if (x == b.x) {
      if (y < b.y) return false;
      if (y > b.y) return true;
      return true;
    }
  }
  bool operator<(point &b) { return (b > point(x, y)); }
  point(long double x1, long double y1) {
    x = x1;
    y = y1;
  }
  long double dist(point b) {
    return sqrt((b.x - x) * (b.x - x) + (y - b.y) * (y - b.y));
  }
  long double dist_kv(point b) {
    return ((b.x - x) * (b.x - x) + (y - b.y) * (y - b.y));
  }
  bool point_on_sig(point &a, point &b) {
    return abs(a.dist(b) - (dist(a) + dist(b))) <= 1e-6;
  }
  long double polar_angle() {
    long double alpha = atan2(y, x);
    long double pi = 3.141592654;
    if (alpha < 0) alpha += 2 * pi;
    return alpha;
  }
};
struct line {
  long double A, B, C;
  line() {
    A = 0;
    B = 0;
    C = 0;
  }
  line(point &a, point &b) {
    A = a.y - b.y;
    B = b.x - a.x;
    C = -A * a.x - B * a.y;
  }
  line(long double a, long double b, long double c) {
    A = a;
    B = b;
    C = c;
  }
  line line_perp_dan_cherez_point(point a) {
    return line(-B, A, -(A * a.y) + B * a.x);
  }
  bool onli(point a) { return A * a.x + B * a.y + C == 0; }
  point intersect_lines(line &a) {
    point p;
    p.x = -(((C * a.B) - (a.C * B)) / ((A * a.B) - (a.A * B)));
    p.y = -(((A * a.C) - (a.A * C)) / ((A * a.B) - (a.A * B)));
    return p;
  }
  bool intersect(line &b) { return A * b.B - B * b.A != 0; }
  bool operator==(line &a) { return A == a.A && B == a.B && C == a.C; }
  long double distance_perpendicular(point &d) {
    return abs(A * d.x + B * d.y + C) / (sqrt(A * A + B * B));
  }
};
struct vc {
  long double x, y;
  vc() {
    x = 0;
    y = 0;
  }
  vc(long double x_, long double y_) {
    x = x_;
    y = y_;
  }
  vc(const point &a) {
    x = a.x;
    y = a.y;
  }
  vc minus(const vc &b) { return vc(x - b.x, y - b.y); }
  long double len() { return sqrt(x * x + y * y); }
  long double scalar(const vc &b) { return x * b.x + y * b.y; }
  long double vector(const vc &b) { return x * b.y - y * b.x; }
  long double angle(const vc &b) { return atan2(vector(b), scalar(b)); }
};
vector<int> top;
void top_sort(int v, vector<int> nodes[], int used[], int colors[]) {
  if (colors[v] == 1) {
    cout << -1;
    exit(0);
  } else if (colors[v] == 0)
    colors[v] = 1;
  for (int i = 0; i < nodes[v].size(); ++i) {
    if (used[nodes[v][i]] == 0) top_sort(nodes[v][i], nodes, used, colors);
  }
  top.push_back(v + 1);
  used[v] = 1;
  colors[v] = 2;
}
vector<int> z_function(string s) {
  vector<int> z(s.size());
  for (int i = 1, l = 0, r = 0; i < s.size(); ++i) {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < s.size() && s[z[i]] == s[i + z[i]]) ++z[i];
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}
vector<int> p_function(string s) {
  vector<int> p(s.size());
  for (int i = 1; i < s.size(); ++i) {
    int j = p[i - 1];
    while (j > 0 && s[i] != s[j]) j = p[j - 1];
    if (s[i] == s[j]) ++j;
    p[i] = j;
  }
  return p;
}
vector<int> now_ans;
void dfsik(int v, vector<int> nodes[], int colors[], int turn) {
  if (colors[v] == 1) {
    now_ans.push_back(0);
    return;
  } else if (colors[v] == 0)
    colors[v] = 1;
  for (int i = 0; i < nodes[v].size(); ++i) {
    if (turn == 1)
      dfsik(nodes[v][i], nodes, colors, 2);
    else
      dfsik(nodes[v][i], nodes, colors, 1);
  }
  if (nodes[v].empty()) {
    now_ans.push_back(turn);
    return;
  }
  colors[v] = 2;
}
long long INF = (long long)1e20;
int int_INF = (int)1e20;
long long t[8 * 100000];
long long ad[8 * 100000];
bool us[8 * 100000];
void build(long long v, long long l, long long r, vector<long long> &a) {
  if (l == r - 1) {
    t[v] = a[l];
    return;
  }
  long long mid = (l + r) / 2;
  build(v * 2, l, mid, a);
  build(v * 2 + 1, mid, r, a);
  t[v] = min(t[2 * v], t[2 * v + 1]);
}
long long mini(long long v, long long l, long long r, long long lf,
               long long rf) {
  if (lf <= l and rf >= r) {
    return t[v];
  }
  if (l >= rf or r <= lf) {
    return INF;
  }
  long long mid = (l + r) / 2;
  return min(mini(v * 2, l, mid, lf, rf), mini(v * 2 + 1, mid, r, lf, rf));
}
void push(long long v, long long l, long long r) {
  if (l == r - 1) {
    ad[2 * v] += ad[v];
    ad[2 * v + 1] += ad[v];
  }
  t[v] += ad[v];
  ad[v] = 0;
}
void push_s(long long v, long long l, long long r) {
  if (!us[v]) return;
  if (l == r - 1) {
    ad[2 * v] += ad[v];
    ad[2 * v + 1] += ad[v];
  }
  t[v] = ad[v];
  ad[v] = 0;
}
void add(long long v, long long l, long long r, long long lf, long long rf,
         long long x) {
  push(v, l, r);
  if (l >= lf and r <= rf) {
    ad[v] += x;
    push(v, l, r);
    return;
  }
  if (l >= rf or r <= lf) return;
  long long mid = (l + r) / 2;
  add(2 * v, l, mid, lf, rf, x);
  add(2 * v + 1, mid, r, lf, rf, x);
  t[v] = min(t[2 * v], t[2 * v + 1]);
}
void sett(long long v, long long l, long long r, long long lf, long long rf,
          long long x) {
  push_s(v, l, r);
  if (l >= lf and r <= rf) {
    ad[v] += x;
    push_s(v, l, r);
    return;
  }
  if (l >= rf or r <= lf) return;
  long long mid = (l + r) / 2;
  add(2 * v, l, mid, lf, rf, x);
  add(2 * v + 1, mid, r, lf, rf, x);
  t[v] = min(t[2 * v], t[2 * v + 1]);
}
int parents[500000];
void create(int v) { parents[v] = v; }
int find_parent(int v) {
  if (v == parents[v]) return v;
  return parents[v] = find_parent(parents[v]);
}
void join(int a, int b) {
  int x = find_parent(a);
  int y = find_parent(b);
  if (x != y) {
    parents[x] = y;
  }
}
vector<long long> manac(string s, int shift) {
  long long l = 0;
  long long r = -1;
  long long n = s.size();
  vector<long long> ans(n);
  for (int i = 1; i < n; i++) {
    long long k = 0;
    if (i <= r) {
      k = min(r - i + shift, ans[r - i + l + shift]);
    }
    while (i - k - 1 >= 0 && i + k + 1 - shift < n &&
           s[i - k - 1] == s[i + k + 1 - shift]) {
      k++;
    }
    if (i + k - shift > r) {
      l = i - k;
      r = i + k - shift;
    }
    ans[i] = k;
  }
  return ans;
}
vector<int> dividers(int x) {
  vector<int> ans;
  ans.push_back(x);
  for (int i = 2; i <= sqrt(x); ++i) {
    if (x % i == 0) {
      ans.push_back(i);
      if (i != sqrt(x)) ans.push_back(x / i);
    }
  }
  return ans;
}
long long max_arr(long long arr[], long long n) {
  long long maxi = -INF;
  for (int i = 0; i < n; ++i) maxi = max(maxi, arr[i]);
  return maxi;
}
long long min_arr(long long arr[], long long n) {
  long long maxi = INF;
  for (int i = 0; i < n; ++i) maxi = min(maxi, arr[i]);
  return maxi;
}
struct triple {
  long long a, b, c;
  triple(long long x, long long y, long long z) {
    a = x;
    b = y;
    c = z;
  }
  triple() {
    a = 0;
    b = 0;
    c = 0;
  }
  bool operator<(const triple *x) { return a < x->a; }
  bool operator==(const triple *x) {
    return a == x->a and b == x->b and c == x->c;
  }
  bool operator>(const triple *x) { return a > x->a; }
};
bool f(int a, int i) { return ((a >> i) & 1); }
long long mex(vector<long long> &kek) {
  vector<long long> cnt(kek.size() + 100);
  for (int i = 0; i < kek.size(); ++i) {
    ++cnt[kek[i]];
  }
  for (int i = 0; i < cnt.size(); ++i) {
    if (cnt[i] == 0) return i;
  }
}
int main() {
  long long t;
  cin >> t;
  for (int i = 0; i < t; ++i) {
    long long a;
    cin >> a;
    cout << (long long)pow(2, __builtin_popcount(a)) << '\n';
  }
}

### Prompt

Create a solution in cpp for the following problem:

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 = 0 for some given a, 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 x, 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 a and your task is to find the number of equation's solution for each of them. The first line contains an integer t (1 ≤ t ≤ 1000) — the number of these values.

The following t lines contain the values of parameter a, each value is an integer from 0 to 2^{30} - 1 inclusive.

Output

For each value of a 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 a appear in the input.

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

Example

Input

3
0
2
1073741823


Output

1
2
1073741824

Note

Let's define the bitwise exclusive OR (XOR) operation. Given two integers x and y, consider their binary representations (possibly with leading zeroes): x_k ... x_2 x_1 x_0 and y_k ... y_2 y_1 y_0. Here, x_i is the i-th bit of the number x and y_i is the i-th bit of the number y. Let r = x ⊕ y be the result of the XOR operation of x and y. Then r is defined as r_k ... r_2 r_1 r_0 where:

$$$ r_i = \left\{ \begin{aligned} 1, ~ if ~ x_i ≠ y_i \\\ 0, ~ if ~ x_i = y_i \end{aligned} \right. $$$

For the first value of the parameter, only x = 0 is a solution of the equation.

For the second value of the parameter, solutions are x = 0 and x = 2.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct point {
  long double x, y;
  point() {
    x = 0;
    y = 0;
  }
  point(long long a, long long b) {
    x = a;
    y = b;
  }
  bool operator==(const point &b) { return x == b.x and y == b.y; }
  bool operator>(const point &b) {
    if (x > b.x) return true;
    if (x < b.x) return false;
    if (x == b.x) {
      if (y < b.y) return false;
      if (y > b.y) return true;
      return true;
    }
  }
  bool operator<(point &b) { return (b > point(x, y)); }
  point(long double x1, long double y1) {
    x = x1;
    y = y1;
  }
  long double dist(point b) {
    return sqrt((b.x - x) * (b.x - x) + (y - b.y) * (y - b.y));
  }
  long double dist_kv(point b) {
    return ((b.x - x) * (b.x - x) + (y - b.y) * (y - b.y));
  }
  bool point_on_sig(point &a, point &b) {
    return abs(a.dist(b) - (dist(a) + dist(b))) <= 1e-6;
  }
  long double polar_angle() {
    long double alpha = atan2(y, x);
    long double pi = 3.141592654;
    if (alpha < 0) alpha += 2 * pi;
    return alpha;
  }
};
struct line {
  long double A, B, C;
  line() {
    A = 0;
    B = 0;
    C = 0;
  }
  line(point &a, point &b) {
    A = a.y - b.y;
    B = b.x - a.x;
    C = -A * a.x - B * a.y;
  }
  line(long double a, long double b, long double c) {
    A = a;
    B = b;
    C = c;
  }
  line line_perp_dan_cherez_point(point a) {
    return line(-B, A, -(A * a.y) + B * a.x);
  }
  bool onli(point a) { return A * a.x + B * a.y + C == 0; }
  point intersect_lines(line &a) {
    point p;
    p.x = -(((C * a.B) - (a.C * B)) / ((A * a.B) - (a.A * B)));
    p.y = -(((A * a.C) - (a.A * C)) / ((A * a.B) - (a.A * B)));
    return p;
  }
  bool intersect(line &b) { return A * b.B - B * b.A != 0; }
  bool operator==(line &a) { return A == a.A && B == a.B && C == a.C; }
  long double distance_perpendicular(point &d) {
    return abs(A * d.x + B * d.y + C) / (sqrt(A * A + B * B));
  }
};
struct vc {
  long double x, y;
  vc() {
    x = 0;
    y = 0;
  }
  vc(long double x_, long double y_) {
    x = x_;
    y = y_;
  }
  vc(const point &a) {
    x = a.x;
    y = a.y;
  }
  vc minus(const vc &b) { return vc(x - b.x, y - b.y); }
  long double len() { return sqrt(x * x + y * y); }
  long double scalar(const vc &b) { return x * b.x + y * b.y; }
  long double vector(const vc &b) { return x * b.y - y * b.x; }
  long double angle(const vc &b) { return atan2(vector(b), scalar(b)); }
};
vector<int> top;
void top_sort(int v, vector<int> nodes[], int used[], int colors[]) {
  if (colors[v] == 1) {
    cout << -1;
    exit(0);
  } else if (colors[v] == 0)
    colors[v] = 1;
  for (int i = 0; i < nodes[v].size(); ++i) {
    if (used[nodes[v][i]] == 0) top_sort(nodes[v][i], nodes, used, colors);
  }
  top.push_back(v + 1);
  used[v] = 1;
  colors[v] = 2;
}
vector<int> z_function(string s) {
  vector<int> z(s.size());
  for (int i = 1, l = 0, r = 0; i < s.size(); ++i) {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < s.size() && s[z[i]] == s[i + z[i]]) ++z[i];
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}
vector<int> p_function(string s) {
  vector<int> p(s.size());
  for (int i = 1; i < s.size(); ++i) {
    int j = p[i - 1];
    while (j > 0 && s[i] != s[j]) j = p[j - 1];
    if (s[i] == s[j]) ++j;
    p[i] = j;
  }
  return p;
}
vector<int> now_ans;
void dfsik(int v, vector<int> nodes[], int colors[], int turn) {
  if (colors[v] == 1) {
    now_ans.push_back(0);
    return;
  } else if (colors[v] == 0)
    colors[v] = 1;
  for (int i = 0; i < nodes[v].size(); ++i) {
    if (turn == 1)
      dfsik(nodes[v][i], nodes, colors, 2);
    else
      dfsik(nodes[v][i], nodes, colors, 1);
  }
  if (nodes[v].empty()) {
    now_ans.push_back(turn);
    return;
  }
  colors[v] = 2;
}
long long INF = (long long)1e20;
int int_INF = (int)1e20;
long long t[8 * 100000];
long long ad[8 * 100000];
bool us[8 * 100000];
void build(long long v, long long l, long long r, vector<long long> &a) {
  if (l == r - 1) {
    t[v] = a[l];
    return;
  }
  long long mid = (l + r) / 2;
  build(v * 2, l, mid, a);
  build(v * 2 + 1, mid, r, a);
  t[v] = min(t[2 * v], t[2 * v + 1]);
}
long long mini(long long v, long long l, long long r, long long lf,
               long long rf) {
  if (lf <= l and rf >= r) {
    return t[v];
  }
  if (l >= rf or r <= lf) {
    return INF;
  }
  long long mid = (l + r) / 2;
  return min(mini(v * 2, l, mid, lf, rf), mini(v * 2 + 1, mid, r, lf, rf));
}
void push(long long v, long long l, long long r) {
  if (l == r - 1) {
    ad[2 * v] += ad[v];
    ad[2 * v + 1] += ad[v];
  }
  t[v] += ad[v];
  ad[v] = 0;
}
void push_s(long long v, long long l, long long r) {
  if (!us[v]) return;
  if (l == r - 1) {
    ad[2 * v] += ad[v];
    ad[2 * v + 1] += ad[v];
  }
  t[v] = ad[v];
  ad[v] = 0;
}
void add(long long v, long long l, long long r, long long lf, long long rf,
         long long x) {
  push(v, l, r);
  if (l >= lf and r <= rf) {
    ad[v] += x;
    push(v, l, r);
    return;
  }
  if (l >= rf or r <= lf) return;
  long long mid = (l + r) / 2;
  add(2 * v, l, mid, lf, rf, x);
  add(2 * v + 1, mid, r, lf, rf, x);
  t[v] = min(t[2 * v], t[2 * v + 1]);
}
void sett(long long v, long long l, long long r, long long lf, long long rf,
          long long x) {
  push_s(v, l, r);
  if (l >= lf and r <= rf) {
    ad[v] += x;
    push_s(v, l, r);
    return;
  }
  if (l >= rf or r <= lf) return;
  long long mid = (l + r) / 2;
  add(2 * v, l, mid, lf, rf, x);
  add(2 * v + 1, mid, r, lf, rf, x);
  t[v] = min(t[2 * v], t[2 * v + 1]);
}
int parents[500000];
void create(int v) { parents[v] = v; }
int find_parent(int v) {
  if (v == parents[v]) return v;
  return parents[v] = find_parent(parents[v]);
}
void join(int a, int b) {
  int x = find_parent(a);
  int y = find_parent(b);
  if (x != y) {
    parents[x] = y;
  }
}
vector<long long> manac(string s, int shift) {
  long long l = 0;
  long long r = -1;
  long long n = s.size();
  vector<long long> ans(n);
  for (int i = 1; i < n; i++) {
    long long k = 0;
    if (i <= r) {
      k = min(r - i + shift, ans[r - i + l + shift]);
    }
    while (i - k - 1 >= 0 && i + k + 1 - shift < n &&
           s[i - k - 1] == s[i + k + 1 - shift]) {
      k++;
    }
    if (i + k - shift > r) {
      l = i - k;
      r = i + k - shift;
    }
    ans[i] = k;
  }
  return ans;
}
vector<int> dividers(int x) {
  vector<int> ans;
  ans.push_back(x);
  for (int i = 2; i <= sqrt(x); ++i) {
    if (x % i == 0) {
      ans.push_back(i);
      if (i != sqrt(x)) ans.push_back(x / i);
    }
  }
  return ans;
}
long long max_arr(long long arr[], long long n) {
  long long maxi = -INF;
  for (int i = 0; i < n; ++i) maxi = max(maxi, arr[i]);
  return maxi;
}
long long min_arr(long long arr[], long long n) {
  long long maxi = INF;
  for (int i = 0; i < n; ++i) maxi = min(maxi, arr[i]);
  return maxi;
}
struct triple {
  long long a, b, c;
  triple(long long x, long long y, long long z) {
    a = x;
    b = y;
    c = z;
  }
  triple() {
    a = 0;
    b = 0;
    c = 0;
  }
  bool operator<(const triple *x) { return a < x->a; }
  bool operator==(const triple *x) {
    return a == x->a and b == x->b and c == x->c;
  }
  bool operator>(const triple *x) { return a > x->a; }
};
bool f(int a, int i) { return ((a >> i) & 1); }
long long mex(vector<long long> &kek) {
  vector<long long> cnt(kek.size() + 100);
  for (int i = 0; i < kek.size(); ++i) {
    ++cnt[kek[i]];
  }
  for (int i = 0; i < cnt.size(); ++i) {
    if (cnt[i] == 0) return i;
  }
}
int main() {
  long long t;
  cin >> t;
  for (int i = 0; i < t; ++i) {
    long long a;
    cin >> a;
    cout << (long long)pow(2, __builtin_popcount(a)) << '\n';
  }
}

```