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

const int maxn=1005;
int T,n,s,ans,tot;
char e[maxn];
int deg[maxn];

namespace Dsu{
    int f[maxn],g[maxn];
    void init(){
        for(int i=1;i<=n;i++)
            f[i]=i,g[i]=1;
    }
    int find(int x){
        return f[x]==x?x:f[x]=find(f[x]);
    }
    void merge(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        f[x]=y;
        g[y]+=g[x];
    }
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&s);
        for(int i=1;i<=n;i++)
            deg[i]=0;
        Dsu::init();
        ans=tot=0;
        for(int i=2;i<=n;i++){
            scanf("%s",e+1);
            for(int j=1;j<i;j++)
                if(e[j]=='0')
                    deg[i]++,deg[j]++,Dsu::merge(i,j),ans++;
        }
        for(int i=1;i<=n;i++){
            tot+=(deg[i]&1);
            if(Dsu::find(i)==i&&Dsu::find(s)!=i&&Dsu::g[i]>1)ans+=2;
        }
        if((deg[s]&1)&&tot!=2){
            puts("-1");
            continue;
        }
        if(!(deg[s]&1)&&tot!=0){
            puts("-1");
            continue;
        }
        printf("%d\n",ans);
    } 
    return 0;
}