/*  
*    The way if it's all predetermined
*    And the way i should go all my life
*    I swear to go wherever will be
*    'Cause there'll be something to see and to find
*/
#include "bits/stdc++.h"
#define ll long long
using namespace std;
#define check(x)                cerr << #x << ": " << x << endl;
#define print(ans)              cout << ans << endl;
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while(t--){
  int n;
  string s;
  cin >> n >> s;
  int m = 1<<n;
  map < deque <char> , int > f;
  for(int i = 1;i<m;i++){
      std::deque<char> k;
      for(int j=0;j<n;j++){
          int x = 1<<j;
          if(x&i)
            k.push_back(s[j]);
      }
      while(k.size() > 1 and k.front() == '0')
        k.pop_front();
      f[k]++;
  }
  cout << f.size();
	}
  cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << "\n";
  return 0;
}