#include <iostream>
#include <string>
using namespace std;

int nc, n, a, b; // a, b is the size of splitting
char c;
bool adjMat[32][32];
int set0[32];
int set1[32];


// for bipartite matching
int matchL[32];
int matchR[32];
bool seen[32];
bool biGraph[32][32];

bool bpm(int i) {
  for(int j = 0; j < b; j++) if(!seen[j] && biGraph[i][j]) {
    seen[j] = true;
    if (matchR[j] < 0 || bpm(matchR[j])) {
      matchL[i] = j;
      matchR[j] = i;
      return true;
    }
  }
  return false;
}

int main() {
  cin >> nc;
  while(nc--) {
    cin >> n;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) {
      cin >> c;
      adjMat[i][j] = (c == '1');
    }

    // try all subsets
    // assume the last communication node is in the 0th set

    int bestMatch = -1;
    for(int mySet = 0; mySet < (1 << n); mySet+=2) {
      a = b = 0;
      for(int i = 0; i < n; i++) {
        if (mySet & (1 << i)) set1[b++] = i;
        else                  set0[a++] = i;
      }

      // no point of trying combinations that can't do better
      if (a <= bestMatch || b <= bestMatch) continue;

      for(int i = 0; i < a; i++) for(int j = 0; j < b; j++)
        biGraph[i][j] = adjMat[set0[i]][set1[j]];
        

      int cnt = 0;
      memset(matchL, -1, sizeof(matchL));
      memset(matchR, -1, sizeof(matchR));
      for(int i = 0; i < a; i++) {
        memset(seen, 0, sizeof(seen));
        if (bpm(i)) cnt++;
      }
      bestMatch >?= cnt;
    }
    cout << bestMatch*2 << endl;
  }
  return 0;
}