#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define LD long double
const LL INF=1e18;
const LD eps=1e-18;
const int N=2e5+10;
const LL P=998244353;
const LD PI=acos(-1.0);
LL qpow(LL x,LL y){
    LL re=1;
    while(y){
        if(y&1) re=re*x%P;
        x=x*x%P;y>>=1;
    }
    return re;
}
int n,S;
char s[1010];
int du[1010];
int fa[1010],cnt[1010];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void MAIN(){
    int u,v,ans=0;
    scanf("%d%d",&n,&S);
    for(int i=1;i<=n;++i){
        du[i]=0;
        fa[i]=i;
        cnt[i]=0;
    }
    for(int i=2;i<=n;++i){
        scanf("%s",s+1);
        for(int j=1;j<i;++j){
            if(s[j]=='0'){
                ++ans;
                ++du[i];
                ++du[j];
                u=find(i);
                v=find(j);
                if(u!=v){
                    fa[v]=u;
                }
                cnt[u]=1;
            }
        }
    }
    int num=0;
    for(int i=1;i<=n;++i){
        if(du[i]&1){
            ++num;
        }
    }
    if(num>2){
        puts("-1");
        return;
    }
    if(num==2){
        if(du[S]%2==0){
            puts("-1");
            return;
        }
    }
    u=find(S);
    cnt[u]=1;
    num=0;
    for(int i=1;i<=n;++i){
        u=find(i);
        if(u!=i) continue;
        if(cnt[i]) num++;
    }
    if(num>1){
        ans+=(num-1)*2;
    }
    printf("%d\n",ans);
    return;
}

int main(){
    //init();
    int ttt=1;scanf("%d",&ttt);
    while(ttt--) MAIN();
    return 0;
}