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).
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Solution{
	
	static int max(int[] arr,int n){
		int mx = Integer.MIN_VALUE;
		for(int i = 0;i < n;i++){
			if(arr[i] > mx){
				mx = arr[i];
			}
		}
		return mx;
	}

	static int min(int[] arr,int n){
		int mn = Integer.MAX_VALUE;
		for(int i = 0;i < n;i++){
			if(arr[i] < mn){
				mn = arr[i];
			}
		}
		return mn;
	}

	static void sort(int[] arr) {
		ArrayList<Integer> l = new ArrayList<>();
		for (int i:arr) l.add(i);
		Collections.sort(l);
		for (int i = 0; i < arr.length; i++) arr[i] = l.get(i);
	}

	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		int nextInt(){
			return Integer.parseInt(next());
		}
		long nextLong(){
			return Long.parseLong(next());
		}
		float nextFloat(){
			return Float.parseFloat(next());
		}
		double nextDouble(){
			return Double.parseDouble(next());
		}
		int[] int_arr(int n){
			int arr[] = new int[n];
			for(int i = 0;i < n;i++) arr[i] = nextInt();
			return arr;
		}
		long[] l_arr(int n){
			long arr[] = new long[n];
			for(int i = 0;i < n;i++) arr[i] = nextLong();
			return arr;
		}
	}

	static int bound(int[] arr,int start,int end,int x,boolean lower){
		int ans = -1;
		while(start <= end){
			int mid = start + (end - start) / 2;
			if(arr[mid] > x) end = mid - 1;
			else if(arr[mid] < x) start = mid + 1;
			else{
				ans = mid;
				if(lower) end = mid - 1;
				else start = mid + 1;
			}
		}
		return ans;
	}

	static boolean isPrime(int n){
        if(n == 1){
            return false;
        }
        if(n == 2 || n == 3){
            return true;
        }
        if(n % 2 == 0 || n % 3 == 0){
            return false;
        }
        for(long i = 5; i*i <= n; i += 6){
            if(n % i == 0 || n % (i + 2) == 0)
                return false;
        }
        return true;
    }

	static int l = 10000000;
	static boolean[] sieve = new boolean[l+1];
	static void primes(){
		Arrays.fill(sieve,true);
		for(int i = 2;i * i <= l;i++){
			if(sieve[i]){
				for(int j = i * i;j <= l;j += i){
					sieve[j] = false;
				}
			}
		}
	}

	public int bs(int[] arr,int start,int end,int target){
		while(start <= end){
			int mid = start + (end - start) / 2;
			if(arr[mid] == target){
				return mid;
			}
			else if(arr[mid] > target){
				end = mid - 1;
			}
			else{
				start = mid + 1;
			}
		}
		return -1;
	}

	public static void main(String[] args){
		FastScanner in = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);

		int t = in.nextInt();
		while(t --> 0){
			int n = in.nextInt();
			long one = 0,zero = 0,ele;
			for(int i = 0;i < n;i++){
				ele = in.nextInt();
				if(ele == 1){
					one += 1l;
				}
				else if(ele == 0){
					zero += 1l;
				}
			}
			System.out.println((1l << zero) * one);
		}
		out.close();
		
    }
}
