#include <bits/stdc++.h>
using namespace std;

int main() {
	int t; // No Of Test Cases
	cin>>t;
	while(t--){
	    int n; // Lenght Of String entered in input
	    cin>>n;
	    string S;
	    cin>>S; // the Original String
	    int count_0=0; // Created a counter for counting no of zeroes
	    int count_1=0; // Created a counter for counting no of ones
	    int n_of_strings=1; // No Of Strings Which are possible, 1 because original string is also counted
	    vector <string> Dummy; // a vector to store newly generated strings
	    Dummy.push_back(S); // Stored Original String
	    int j=0;
	    while(j<Dummy.size()){
	        string y=Dummy[j]; // Started with my original string
	        count_0=0;
    	    count_1=0;
    	    for(int i=0;i<n;i++){
                // Counting No of zeroes and 1s
    	        if(Dummy[j][i]=='0'){
    	            count_0+=1;
    	        }
    	        else if(Dummy[j][i]=='1'){
    	            count_1+=1;
    	        }
                // if both count are equal then flip also there count shouldnt equal to 0
    	        if (count_0==count_1 && count_1!=0){
    	            for(int k=0;k<count_0*2;k++){ // *2 because number of zeroes and no of 1s both have to be flipped
    	                    if (y[k]=='0'){ // 0 to 1
    	                        y[k]='1';
    	                    }
    	                    else if(y[k]=='1'){ 0 //1 to 0
    	                        y[k]='0';
    	                    }
    	                }
    	            bool exists = find(Dummy.begin(), Dummy.end(), y) != Dummy.end(); // checking if the generated string exists in vector or is it a new one
    	            if (exists){
    	                continue;
    	            }
    	            else{
    	                Dummy.push_back(y);
    	                n_of_strings+=1;
    	                i=-1;
    	                count_0=0;
    	                count_1=0;
    	            }
    	        }
    	    }
    	    j++;
	    }
	    cout<<n_of_strings<<endl;
	}

}