/*  
*    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;
}  

LyogIAoqICAgIFRoZSB3YXkgaWYgaXQncyBhbGwgcHJlZGV0ZXJtaW5lZAoqICAgIEFuZCB0aGUgd2F5IGkgc2hvdWxkIGdvIGFsbCBteSBsaWZlCiogICAgSSBzd2VhciB0byBnbyB3aGVyZXZlciB3aWxsIGJlCiogICAgJ0NhdXNlIHRoZXJlJ2xsIGJlIHNvbWV0aGluZyB0byBzZWUgYW5kIHRvIGZpbmQKKi8KI2luY2x1ZGUgImJpdHMvc3RkYysrLmgiCiNkZWZpbmUgbGwgbG9uZyBsb25nCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgY2hlY2soeCkgICAgICAgICAgICAgICAgY2VyciA8PCAjeCA8PCAiOiAiIDw8IHggPDwgZW5kbDsKI2RlZmluZSBwcmludChhbnMpICAgICAgICAgICAgICBjb3V0IDw8IGFucyA8PCBlbmRsOwppbnQgbWFpbigpewogIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogIGNpbi50aWUoTlVMTCk7CiAgaW50IHQ7CiAgY2luID4+IHQ7CiAgd2hpbGUodC0tKXsKICBpbnQgbjsKICBzdHJpbmcgczsKICBjaW4gPj4gbiA+PiBzOwogIGludCBtID0gMTw8bjsKICBtYXAgPCBkZXF1ZSA8Y2hhcj4gLCBpbnQgPiBmOwogIGZvcihpbnQgaSA9IDE7aTxtO2krKyl7CiAgICAgIHN0ZDo6ZGVxdWU8Y2hhcj4gazsKICAgICAgZm9yKGludCBqPTA7ajxuO2orKyl7CiAgICAgICAgICBpbnQgeCA9IDE8PGo7CiAgICAgICAgICBpZih4JmkpCiAgICAgICAgICAgIGsucHVzaF9iYWNrKHNbal0pOwogICAgICB9CiAgICAgIHdoaWxlKGsuc2l6ZSgpID4gMSBhbmQgay5mcm9udCgpID09ICcwJykKICAgICAgICBrLnBvcF9mcm9udCgpOwogICAgICBmW2tdKys7CiAgfQogIGNvdXQgPDwgZi5zaXplKCk7Cgl9CiAgY2VyciA8PCAidGltZSB0YWtlbiA6ICIgPDwgKGZsb2F0KWNsb2NrKCkgLyBDTE9DS1NfUEVSX1NFQyA8PCAiIHNlY3MiIDw8ICJcbiI7CiAgcmV0dXJuIDA7Cn0gIA==

MQoxNyAKMTAxMTAwMTEwMTEwMTExMDE=

1
17 
10110011011011101