#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

//#include <atcoder/convolution>
//#include <atcoder/modint> 
//using Modint = atcoder::modint998244353;

using namespace std;
typedef long long ll;

void ex_gcd(ll a, ll b, ll &d, ll &x, ll &y) {
  if (!b) {
    d = a;
    x = 1;
    y = 0;
  } else {
    ex_gcd(b, a % b, d, y, x);
    y -= a / b * x;
  }
}
ll inv(ll a, ll n) {
  ll d, x, y;
  ex_gcd(a, n, d, x, y);
  return d == 1 ? (x % n + n) % (n / d) : -1;
}
ll gcd(ll x, ll y) {
  if (y == 0) return x;
  return gcd(y, x % y);
}

int gcd(int x, int y) {
  if (y == 0) return x;
  return gcd(y, x % y);
}

inline void scan_d(int &ret) {
    char c; ret=0;
    while((c=getchar())<'0'||c>'9');
    while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
}

const int maxn = 1005;
const int mod = 998244353;

int d[maxn];
int f[maxn];
int cc[maxn];

int pd(int x){
  if(f[x]!=x)f[x] = pd(f[x]);
  return f[x];
}

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.cpp", "r", stdin);
  freopen("/Users/suiyuan2009/CLionProjects/icpc/output.cpp", "w", stdout);
#endif
  int T;
  cin>>T;
  while(T--){
    int n,st;
    cin>>n>>st;
    for(int i=1;i<=n;i++){
      f[i] = i;
      d[i] = 0;
      cc[i] = 1;
    }
    int ret = 0;
    for(int i=2;i<=n;i++){
      string s;
      cin>>s;
      for(int j=0;j<s.size();j++){
        int tt = s[j] - '0';
        d[i] += (tt==1?2:1);
        d[j+1] += (tt==1?2:1);
        if(tt==0){
          ret++;
          int px = pd(j+1);
          int py = pd(i);
          if(px!=py) {
            f[px] = py;
            cc[py] += cc[px];
          }
        }
      }
    }
    int odd = 0;
    for(int i=1;i<=n;i++){
      if(d[i]&1)odd++;
    }
    if(odd>2||(odd==2&&d[st]%2==0)){
      cout<<-1<<endl;
    } else {
      for(int i=1;i<=n;i++){
        int px = pd(i);
        int py = pd(st);
        if(px!=py&&px==i&&cc[i]>1)ret+=2;
      }
      cout<<ret<<endl;
    }
  }
  return 0;
}