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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.*;

public class Mainnn {

    // static final File ip = new File("input.txt");
    // static final File op = new File("output.txt");
    // static {
    //     try {
    //         System.setOut(new PrintStream(op));
    //         System.setIn(new FileInputStream(ip));
    //     } catch (Exception e) {
    //     }

    //     // in = new InputReader(System.in);
    // }
    private static final PrintWriter out = new PrintWriter(System.out);


    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        // out = new PrintWriter(new BufferedOutputStream(System.out));

        // out.println(result); // print via PrintWriter
        /////////////////////////////////////////////

        int test = sc.nextInt();
        while (test-- != 0) {
            int n = sc.nextInt();
            long[] a = new long[n];
            long one=0,zero=0;
            int f = 0;
            for(int i=0;i<n;i++)
            {
                a[i] = sc.nextLong();
                if(a[i] == 1) one++;
                else if(a[i] == 0) zero++;
                else f=1;
            }
            if(one==0) System.out.println(0);
            else if(zero == 0) System.out.println(one);
            else
            {
                // if(one==1 && zero==1) System.out.println(2);
                // else if(one == 1) System.out.println(one+((long) Math.pow(2, zero)-1)*one+1);
                // else System.out.println(one+((long) Math.pow(2, zero)-1)*one);
                System.out.println(one+((long) Math.pow(2, zero)-1)*one);
            }
        }
    }

    static long power(long x, long y, long p) {
        long res = 1;
        x = x % p;
        if (x == 0)
            return 0;
        while (y > 0) {
            if ((y & 1) != 0)
                res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    static void sortI(int[] arr) {
        int n = arr.length;
        Random rnd = new Random();
        for (int i = 0; i < n; ++i) {
            int tmp = arr[i];
            int randomPos = i + rnd.nextInt(n - i);
            arr[i] = arr[randomPos];
            arr[randomPos] = tmp;
        }
        Arrays.sort(arr);
    }

    static void sortL(long[] arr) {
        int n = arr.length;
        Random rnd = new Random();
        for (int i = 0; i < n; ++i) {
            long tmp = arr[i];
            int randomPos = i + rnd.nextInt(n - i);
            arr[i] = arr[randomPos];
            arr[randomPos] = tmp;
        }
        Arrays.sort(arr);
    }

    private static long gcd(long a, long b) {
        return (a == 0 ? b : gcd(b % a, a));
    }

    static class pair implements Comparator<pair> {
        long a;
        int b;

        pair(long x, int y) {
            this.a = x;
            this.b = y;
        }

        public int compare(pair p1, pair p2) {
            if (p1.a > p2.a)
                return 1;
            else if (p1.a < p2.a)
                return -1;
            return 0;
        }
    }

    static class first implements Comparator<pair> {

        public int compare(pair p1, pair p2) {
            if (p1.a > p2.a)
                return 1;
            else if (p1.a < p2.a)
                return -1;
            return 0;
        }
    }

    static class second implements Comparator<pair> {

        public int compare(pair p1, pair p2) {
            if (p1.b > p2.b)
                return 1;
            else if (p1.b < p2.b)
                return -1;
            return 0;
        }
    }

    // -----------PrintWriter for faster output---------------------------------

    // -----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                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());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }
    // --------------------------------------------------------
}