Luntik came out for a morning stroll and found an array a of length n. He calculated the sum s of the elements of the array (s= ∑_{i=1}^{n} a_i). Luntik calls a subsequence of the array a nearly full if the sum of the numbers in that subsequence is equal to s-1.

Luntik really wants to know the number of nearly full subsequences of the array a. But he needs to come home so he asks you to solve that problem!

A sequence x is a subsequence of a sequence y if x can be obtained from y by deletion of several (possibly, zero or all) elements.

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases. The next 2 ⋅ t lines contain descriptions of test cases. The description of each test case consists of two lines.

The first line of each test case contains a single integer n (1 ≤ n ≤ 60) — the length of the array.

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 10^9) — the elements of the array a.

Output

For each test case print the number of nearly full subsequences of the array.

Example

Input


5
5
1 2 3 4 5
2
1000 1000
2
1 0
5
3 0 2 1 1
5
2 1 0 3 0


Output


1
0
2
4
4

Note

In the first test case, s=1+2+3+4+5=15, only (2,3,4,5) is a nearly full subsequence among all subsequences, the sum in it is equal to 2+3+4+5=14=15-1.

In the second test case, there are no nearly full subsequences.

In the third test case, s=1+0=1, the nearly full subsequences are (0) and () (the sum of an empty subsequence is 0).
#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, -1, 0, 1};
unsigned long long GCD(unsigned long long x, unsigned long long y) {
  if (y == 0)
    return x;
  else
    return GCD(y, x % y);
}
unsigned long long LCM(unsigned long long a, unsigned long long b) {
  return (a * b / (GCD(a, b)));
}
bool PRIME(int p) {
  if (p <= 1) return false;
  if (p <= 3) return true;
  if (p % 2 == 0 || p % 3 == 0) return false;
  for (int i = 5; p >= i * i; i = i + 6) {
    if (p % i == 0 || p % (i + 2) == 0) return false;
  }
  return true;
}
long long NXT(long long a) {
  if (a <= 1) return 2;
  long long p = a;
  bool x = false;
  while (!x) {
    p++;
    if (PRIME(p)) x = true;
  }
  return p;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  long long a, b, c, d, e, t, i, j, k, l, p, q, r,
      sum = 0, ans = 0, x, y, z, m, n, o, u, mx = -1e10, mn = 1e9;
  t = 1;
  cin >> t;
  while (t--) {
    cin >> n;
    long long A[113];
    x = y = sum = 0;
    for (i = 0; i < n; i++) {
      cin >> A[i];
      if (A[i] == 1)
        x++;
      else if (A[i] == 0)
        y++;
      sum += A[i];
    }
    if (sum == 0 || x == 0) {
      cout << 0 << endl;
      continue;
    }
    if (y == 0) {
      cout << x << endl;
    } else {
      if (x > 1)
        p = pow(2, x - 1);
      else
        p = 1;
      q = pow(2, y);
      cout << p * q << endl;
    }
  }
  return 0;
}
