#include<bits/stdc++.h>
#define LL long long
#define dl double
#define Pi pair<int,int>
#define SZ(a) ((int)a.size())
using namespace std;

const int N = 1005;

int T;
int n,s;
int a[N][N];
int in[N];
bool vis[N];
void dfs(int x){
  vis[x] = 1;
  for(int i = 1;i <= n;i++)
    if(a[x][i] && !vis[i])dfs(i);
}
int work(){
  int cnt = 0;
  for(int i = 1;i <= n;i++)if(in[i] & 1)cnt++;
  if(cnt != 0 && cnt != 2)return -1;
  memset(vis,0,sizeof(vis));
  int now = 0;
  for(int i = 1;i <= n;i++){
    if(!in[i] || vis[i])continue;
    dfs(i);now++;
  }
  if(now == 0)return 0;
  if(cnt && in[s] % 2 == 0)return -1;
  if(!in[s])now++;
  int ret = 0;
  for(int i = 1;i <= n;i++)
    for(int j = i + 1;j <= n;j++)
      if(a[i][j])ret++;
  return ret + (now - 1) * 2;
}

int main(){
  // freopen("in.txt","r",stdin);
  // freopen("o.txt","w",stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  cin >> T;
  while(T--){
    cin >> n >> s;
    for(int i = 2;i <= n;i++){
      char str[N];cin >> (str + 1);
      for(int j = 1;j < i;j++)a[i][j] = a[j][i] = (str[j] - '0') ^ 1;
    }
    memset(in,0,sizeof(in));
    for(int i = 1;i <= n;i++)
      for(int j = 1;j <= n;j++)
        if(a[i][j])in[i]++;
    cout << work() << endl;
  }
  return 0;
}
/**/