#include<bits/stdc++.h>
using namespace std;

typedef long long s64;
const int N=1000+5,D=998244353;
s64 pow_mod(s64 x,int y){
    s64 ans=1;
    while(y){
        if(y&1)ans=ans*x%D;
        x=x*x%D;y>>=1;
    }
    return ans;
}
char str[N];
int du[N],fa[N],sz[N];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

int main(){
#ifdef kcz
    freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
#endif
    int tt;
    cin>>tt;
    while(tt--){
        int n,s;
        cin>>n>>s;
        memset(du,0,sizeof(du));
        memset(sz,0,sizeof(sz));
        for(int i=1;i<=n;++i)fa[i]=i;
        int ans=0;
        for(int i=1;i<n;++i){
            scanf("%s",str+1);
            for(int j=1;j<=i;++j)
            if(str[j]=='0'){
                int x=find(i+1),y=find(j);
                fa[x]=y;
                ++du[i+1];++du[j];
                ++ans;
            }
        }
        int cnt=0;
        for(int i=1;i<=n;++i)
        if(i!=s&&du[i]%2)++cnt;
        if(cnt>1){
            puts("-1");
            continue;
        }
        ans-=2;
        for(int i=1;i<=n;++i)sz[find(i)]+=1+(i==s);
        for(int i=1;i<=n;++i)ans+=(fa[i]==i&&sz[i]>1)*2;
        cout<<ans<<endl;
    }
}