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.*;
    import java.util.*;

    import static java.lang.System.*;
    import static java.lang.Math.*;
    import static java.util.Collections.*;
    import static java.util.Arrays.*;
    public class B {
        public static int swap(int... args) {
            return args[0];
        } static   ArrayList<Integer> primes = new ArrayList<>();
        //static Scanner sc = new Scanner(System.in);
        static FastReader sc = new FastReader();
        public static void main(String[] args) throws IOException {
            do {
                startTime = currentTimeMillis();
                //setOut(new PrintStream("output"));
                //setIn(new FileInputStream("input"));
               int T = sc.nextInt(); while (T-- != 0)
                {
                    solve();

                }
                endTime = currentTimeMillis();
                long duration = endTime - startTime;
                //out.println(duration);
                if (false) {
                    out.println(max(3, 2));
                    Integer[] ARRAY = new Integer[2];
                    ArrayList<Integer> LIST = new ArrayList<>();
                    LIST.add(2);
                    // sort(LIST, reverseOrder());
                    LIST.sort(reverseOrder());
                    sort(ARRAY, reverseOrder());
                    out.println(LIST + " " + Arrays.toString(ARRAY));
                }
            } while (LOCAL);
        }


        public static void solve() throws IOException {
    /////////////////////////////////////////////////////////////////////
            int n =sc.nextInt();
            int [] arr = new int[n];
            long zeros=0,ones=0;
            for (int i = 0; i < n; i++) {
                arr[i]=sc.nextInt();
                if(arr[i]==0)zeros++;
                else if(arr[i]==1)ones++;
            }
            out.println(ones*power1(2,zeros,Long.MAX_VALUE));
    ///////////////////////////////////////////////////////////////////////

        }

        public static final boolean LOCAL = System.getProperty("ONLINE_JUDGE")==null;
        // public static final boolean LOCAL = System.getProperty("LOCAL")!=null;
        public static final String ANSI_RED = "\u001B[31m";
        public static final String ANSI_RESET = "\u001B[0m";
        static long startTime;
        static long endTime;
        static boolean[] prime;
        static final int M = (int) 1e9 + 7;
        static final long MM = (long) M * M;
        static final int MAX = Integer.MAX_VALUE;
        static final int MIN = Integer.MIN_VALUE;
        static final int SIZE = (int) 1e9 * 2;
        static int [] visited;
        static ArrayList<ArrayList<Integer>> graph;
        static ArrayList<Integer> dfs;
        static  boolean isCyclic = false;
        static void dfs(int src){
            visited[src] = 1;
            for(Integer integer : graph.get(src) ){
                if(visited[integer]!=1){
                    dfs(integer);
                }
            }
            dfs.add(src);

        }
        static void detectCycle(int src){
            visited[src] =2;
            for(Integer integer : graph.get(src)){
                if(visited[integer]==0){
                    detectCycle(integer);
                }
                else if(visited[integer]==2) {
                    isCyclic = true;
                    return;
                }

            }
            visited[src] = 1;
        }
        static class FastReader {
            BufferedReader br;
            StringTokenizer st;
            public FastReader() {
                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;
            }
        }

        static class Pair implements Comparable< Pair> {
            private int ID;
            private int wins;

            public void setID(int ID) {
                this.ID = ID;
            }

            public void setWins(int wins) {
                this.wins = wins;
            }

            public Pair(int ID, int value) {
                this.ID = ID;
                this.wins = value;
            }
            public int second() {
                return wins;
            }
            @Override
            public int compareTo(Pair o) {
                //   out.println(o.wins +" " + wins);
                int winVal = Integer.compare(o.wins, wins);
                //  dbg(winVal);
                if(winVal==0){
                    return -Integer.compare(o.ID,ID);
                }
                return winVal;
            }
            @Override
            public String toString() {
                return "Pair{" + "x=" + ID + ", y=" + wins + '}';
            }
        }
        static <Array, Target> int count(Array[] array, Target target){
            int cn=0;
            for (Array value : array) {
                if (value.equals(target)) cn++;
            }
            return cn;
        }
        static int count (String string , char target){
            int cn=0;
            for (int i = 0; i < string.length(); i++) {
                if(string.charAt(i)==target)cn++;
            }
            return cn;
        }
        static  <Array> void revArray(Array [] arr) {
            int n = arr.length;
            for (int i = 0; i < n / 2; i++) {
                Array temp = arr[i];
                arr[i] = arr[n - i - 1];
                arr[n - i - 1] = temp;
            }

        }
        static <Array> void printArray(Array [] arr) {
            int n = arr.length;
            for (Array array : arr)out.print(array + " ");
            out.println();
        }
        static void yes() {out.println("YES");}
        static void no() {out.println("NO");}
        public static boolean isPal(String s)
        {
            StringBuilder stringBuilder = new StringBuilder(s);
            return s.equals(stringBuilder.reverse().toString());
        }
        public static int lowerBound(Integer[] array, int length, int value) {
            int low = -1;
            int hi = length;
            while (low + 1 < hi) {
                int mid = (low + hi) / 2;
                if (array[mid] <= value) {
                    low = mid;
                } else {
                    hi = mid;
                }
            }
            return low;
        }
        public static int upperBound(Integer[] array, int length, int value) {
            int low = -1;
            int hi = length;
            while (low + 1 < hi) {
                int mid = (low + hi) >> 1;
                if (array[mid] >= value) {
                    hi = mid;
                } else low = mid;
            }
            return hi;
        }
        public static int binarySearch(Integer[] arr, int length, int value) {
            int low = 0;
            int hi = length - 1;
            int ans = -1;
            while (low <= hi) {
                int mid = (low + hi) >> 1;
                if (arr[mid] > value) {
                    hi = mid - 1;
                } else if (arr[mid] < value) {
                    low = mid + 1;
                } else {
                    ans = mid;
                    break;
                }
            }
            return ans;
        }
        public static int gcd(int a, int b) {
            return b==0?a:gcd(b, a % b);
        }
        public static int lcm(int a, int b) {
            return a / gcd(a, b) * b;
        }
        public static int countDivs(int n) {
            int cn = 0;
            int sqr = (int) Math.sqrt(n);
            for (int i = 1; i <= sqr; ++i) {
                if (n % i == 0) {
                    ++cn;
                }
            }
            cn *= 2;
            if (sqr * sqr == n) cn--;
            return cn;
        }

        static void prime(int x) {
            //sieve algorithm. nlog(log(n)).
            prime = new boolean[(x + 1)];
            Arrays.fill(prime, true);
            prime[0] = prime[1] = false;
            for (int i = 2; i * i <= x; i++)
                if (prime[i])
                    for (int j = i * i; j <= x; j += i)
                        prime[j] = false;
        }
        static boolean isEven(long x) {
            return x % 2 == 0;
        }
        static boolean isPrime(long x) {
            boolean flag = true;
            int sqr = (int) Math.sqrt(x);
            if (x < 2) return false;
            for (int i = 2; i <= sqr; i++) {
                if (x % i == 0) {
                    flag = false;
                    break;
                }
            }
            return flag;
        }

        static long factorial(long x) {
            long total = 1;
            for (int i = 2; i <= x; i++)
                total = (total * i) % M;
            return total;
        }
        static long power1(long x, long y, long p)
        {
            long res = 1; // Initialize result

            x = x % p; // Update x if it is more than or
            // equal to p

            if (x == 0)
                return 0; // In case x is divisible by p;

            while (y > 0)
            {

                // If y is odd, multiply x with result
                if ((y & 1) != 0)
                    res = (res * x) % p;

                // y must be even now
                y = y >> 1; // y = y/2
                x = (x * x) % p;
            }
            return res;
        }
        static long power(long x, long n) {
            if (n == 0) {
                return 1;
            }
            long pow = power(x, n / 2L);
            if ((n & 1) == 1) {
                return (x%MM * (pow%MM) * (pow%MM))%MM;
            }
            return (pow%MM * pow%MM)%MM;
        }
        private static <T> String ts(T t) {
            if(t==null) {
                return "null";
            }
            try {
                return ts((Iterable) t);
            }catch(ClassCastException e) {
                if(t instanceof int[]) {
                    String s = Arrays.toString((int[]) t);
                    return "{"+s.substring(1, s.length()-1)+"}";
                }else if(t instanceof long[]) {
                    String s = Arrays.toString((long[]) t);
                    return "{"+s.substring(1, s.length()-1)+"}";
                }else if(t instanceof char[]) {
                    String s = Arrays.toString((char[]) t);
                    return "{"+s.substring(1, s.length()-1)+"}";
                }else if(t instanceof double[]) {
                    String s = Arrays.toString((double[]) t);
                    return "{"+s.substring(1, s.length()-1)+"}";
                }else if(t instanceof boolean[]) {
                    String s = Arrays.toString((boolean[]) t);
                    return "{"+s.substring(1, s.length()-1)+"}";
                }
                try {
                    return ts((Object[]) t);
                }catch(ClassCastException e1) {
                    return t.toString();
                }
            }
        }
        private static <T> String ts(T[] arr) {
            StringBuilder ret = new StringBuilder();
            ret.append("{");
            boolean first = true;
            for(T t: arr) {
                if(!first) {
                    ret.append(", ");
                }
                first = false;
                ret.append(ts(t));
            }
            ret.append("}");
            return ret.toString();
        }
        private static <T> String ts(Iterable<T> iter) {
            StringBuilder ret = new StringBuilder();
            ret.append("{");
            boolean first = true;
            for(T t: iter) {
                if(!first) {
                    ret.append(", ");
                }
                first = false;
                ret.append(ts(t));
            }
            ret.append("}");
            return ret.toString();
        }
        public static void dbg(Object... o) {
            if(LOCAL) {
                System.err.print("Line #"+Thread.currentThread().getStackTrace()[2].getLineNumber()+": [");
                for(int i = 0; i<o.length; i++) {
                    if(i!=0) {
                        System.err.print(", ");
                    }
                    System.err.print(ts(o[i]));
                }
                System.err.println("]");
            }
        }

    }
