#include <cstdio>
#include <algorithm>
#include <cstring>

int T,cnt;
int f[1001],d[1001],c[1001];
int find(int x){
    return f[x]?f[x]=find(f[x]):x;
}
void merge(int a,int b){
    a=find(a),b=find(b);
    if(a!=b)f[a]=b;
}
int n,s,g[1001];
bool vis[1001];
bool con[1001][1001];
char str[1001];
int main(){
    scanf("%d",&T);
    for(int fd=1;fd<=T;++fd){
        scanf("%d%d",&n,&s);
        cnt=0;
        memset(vis,0,sizeof vis);
        memset(c,0,sizeof c);
        memset(g,0,sizeof g);
        vis[s]=1;
        memset(f,0,sizeof f);
        memset(d,0,sizeof d);
        for(int i=2;i<=n;++i){
            scanf("%s",str+1);
            for(int j=1;j<i;++j){
                con[i][j]=con[j][i]=(str[j]=='1');
                if(!con[i][j]){
                    ++cnt,vis[i]=vis[j]=1,merge(i,j);
                    d[i]^=1,d[j]^=1;
                }
            }
        }
        bool ans=1;
        int Cnt=0;
        for(int i=1;i<=n;++i)if(d[i])++Cnt;
        if(Cnt-((d[s]==1)*2)){
            puts("-1");
            continue;
        }
        for(int i=1;i<=n;++i)
            if(!f[i]&&vis[i])cnt+=2;
        printf("%d\n",cnt-2);
    }
}