#include<bits/stdc++.h>
using namespace std;
const int N=5+1e3;
vector<int> e[N];
bool vis[N];
char ss[N];
void dfs(int x){
    if(vis[x]) return;
    vis[x]=1; 
    for(auto y:e[x])
        dfs(y);
}
void solve(){
    int n,s,ans=0; scanf("%d%d",&n,&s);
    for(int i=1;i<=n;++i) vis[i]=0,e[i].clear();
    for(int i=2;i<=n;++i){
        scanf("%s",ss+1);
        for(int j=1;j<i;++j)
            if(ss[j]=='0'){
                e[i].push_back(j);
                e[j].push_back(i);
                ++ans;
            }
    }
    dfs(s);
    int odd_cnt=0;
    for(int x=1;x<=n;++x)
        if(e[x].size()&1){
            if(!vis[x]){
                puts("-1");
                return;
            }
            ++odd_cnt;
        }
    assert(~odd_cnt&1);
    if(odd_cnt>2){
        puts("-1");
        return;
    }else if(odd_cnt==2){
        if(e[s].size()&1);
        else{
            puts("-1");
            return;
        }
    }
    for(int x=1;x<=n;++x)
        if(!vis[x]&&e[x].size()>0){
            dfs(x);
            ans+=2;
        }
    printf("%d\n",ans);
}
int main(){
    int T; scanf("%d",&T);
    while(T--) solve();
    return 0;
}