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.util.Scanner;
import java.util.StringTokenizer;
import java.io.*;
import java.util.*;
import java.text.DecimalFormat;
import java.math.*;

public class Main {

static int  mod = 1000000007;
/*****************code By Priyanshu *******************************************/ 

    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;
        }
    }
    // this > other return +ve
    // this < other return -ve
    // this == other return 0
     public static class Pair implements Comparable<Pair> {
      long st;
      long et;

      public Pair(long st, long et) {
         this.st = st;
         this.et = et;
      }

      public int compareTo(Pair other) {
         if (this.st != other.st) {
            return (int)(this.st - other.st);
         } else {
            return (int)(this.et - other.et);
         }
      }
   }

    static long fastPower(long a, long b, int n) {
            
            long res = 1;
            
            while ( b > 0) {
                
                if ( (b&1) != 0) {
                    res = (res * a % n) % n;
                }
                
                a = (a % n * a % n) % n;
                b =  b >> 1;
            }
            
            return res;
            
        }

     // function to find
    // the rightmost set bit
    static int PositionRightmostSetbit(int n)
    {
        // Position variable initialize
        // with 1 m variable is used to
        // check the set bit
        int position = 1;
        int m = 1;
 
        while ((n & m) == 0) {
 
            // left shift
            m = m << 1;
            position++;
        }
        return position;
    }
    
         // used for swapping ith and jth elements of array
      // public static void swap(int[] arr, int i, int j) {
      //   int temp = arr[i];
      //   arr[i] = arr[j];
      //   arr[j] = temp;
      // }
        public static void swap(long i, long j) {
        long temp = i;
        i = j;
        j = temp;
      }


    static boolean palindrome(String s) {
        return new StringBuilder(s).reverse().toString().equals(s);
    }
    
  static boolean isPerfectSquare(double x)
    {
            double sr = Math.sqrt(x);
            return ((sr * sr) == x);     
    }


 public static long gcd(long a, long b)
    {
      if (b == 0)
        return a;
      return gcd(b, a % b);
    }
    
   

   static int nod(long l) {
       if(l>=1000000000000000000l) return 19;
       if(l>=100000000000000000l) return 18;
       if(l>=10000000000000000l) return 17;
       if(l>=1000000000000000l) return 16;
       if(l>=100000000000000l) return 15;
       if(l>=10000000000000l) return 14;
       if(l>=1000000000000l) return 13;
       if(l>=100000000000l) return 12;
       if(l>=10000000000l) return 11;
       if(l>=1000000000) return 10;
       if(l>=100000000) return 9;
       if(l>=10000000) return 8;
       if(l>=1000000) return 7;
       if(l>=100000) return 6;
       if(l>=10000) return 5;
       if(l>=1000) return 4;
       if(l>=100) return 3;
       if(l>=10) return 2;
       return 1;
    }
      //Arrays.sort(a,(c,d) -> Integer.compare(c[0],d[0]));

    
    public static boolean areAllBitsSet(int n )
    {
        // all bits are not set
        if (n == 0)
            return false;
     
        // if true, then all bits are set
        if (((n + 1) & n) == 0)
            return true;
     
        // else all bits are not set
        return false;
    }

     public static long[] sort(long[] arr) {
        List<Long> temp = new ArrayList();
        for (long i : arr) temp.add(i);
        Collections.sort(temp);
        int start = 0;
        for (long i : temp) arr[start++] = i;
        return arr;
    }
   
 

        public static int[] radixSort2(int[] a)
    {
        int n = a.length;
        int[] c0 = new int[0x101];
        int[] c1 = new int[0x101];
        int[] c2 = new int[0x101];
        int[] c3 = new int[0x101];
        for(int v : a) {
            c0[(v&0xff)+1]++;
            c1[(v>>>8&0xff)+1]++;
            c2[(v>>>16&0xff)+1]++;
            c3[(v>>>24^0x80)+1]++;
        }
        for(int i = 0;i < 0xff;i++) {
            c0[i+1] += c0[i];
            c1[i+1] += c1[i];
            c2[i+1] += c2[i];
            c3[i+1] += c3[i];
        }
        int[] t = new int[n];
        for(int v : a)t[c0[v&0xff]++] = v;
        for(int v : t)a[c1[v>>>8&0xff]++] = v;
        for(int v : a)t[c2[v>>>16&0xff]++] = v;
        for(int v : t)a[c3[v>>>24^0x80]++] = v;
        return a;
    } 

    public static void print( int arr[] ){
        Arrays.stream(arr).forEach(str -> System.out.print(str + " "));
    }

    static boolean isPowerOfTwo (int x)
    {
      /* First x in the below expression is 
        for the case when x is 0 */
        return x!=0 && ((x&(x-1)) == 0);
          
    }

   

  static class Help {
    int index;
    int val;
    int res ;
    //Constructor
    Help(int i, int v) {
      index = i;
      val = v;
      res = 0;
    }
  }



  public static void main(
        String[] args)
    {
        try {
            System.setIn(new FileInputStream("input.txt"));
            System.setOut(new PrintStream(new FileOutputStream("output.txt")));
        } catch (Exception e) {
            System.err.println("Error");
        }
         
       FastReader sc = new FastReader();
        int t = Integer.parseInt(sc.next());
      // int t = 1;
       // StringBuilder ans = new StringBuilder();
  //  ArrayList<Integer> a = new ArrayList<>();
    
   while(t-->0){
    int n = sc.nextInt();
      // int a = sc.nextInt();
      //  int b = sc.nextInt();
      //   int c = sc.nextInt();

        // if(2*b <= (3*c+1)){
        //   System.out.println("0");
        // }

         // int  ar = a%2;
         // int br = b%2;
      int m[] = new int[4];
         // int  cr = c%2;
     Arrays.fill(m,0);
     radixSort2(m);
     radixSort2(m);
        
       
          int a[] = new int[n];
           int count1=0,count0=0;
      for(int i = 0;i<n;i++){
        a[i] = sc.nextInt();
        if(a[i] == 1){
          count1++;
        }
        if(a[i] == 0){
          count0++;
        }
        
      }

       if(count0 > 0 && count1 >0)
    {
           radixSort2(m);
        System.out.println((long)(Math.pow(2,count0)*count1));
    }
    else
    {   radixSort2(m);
        System.out.println(count1);
    }

      
    //       if(ar == 1 && br == 1 && cr == 1)
    // {
    //     System.out.println("0");
    // }
    // else if(((ar ==1 && br == 1)) || (br ==1&& cr ==1))
    // {
    //     System.out.println("1");
    // }
    // else if(ar ==1 &&  cr==1)
    // {
    //     System.out.println("2");
    // }
    // else
    // {
    //    System.out.println("0");
    // }












    
    }
  }
}






//code By Priyanshu 

