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

typedef long long ll;

int i,j,k,n,m,t,st,sb,num[2050],it1,it2,res,tmp;
bool f[1050][1050],vis[1050];
char c;

void dfs(int x){
    vis[x]=1;
    if(num[x]&1){it2++;}
    if(x==st){it1=1;}
    for(int i=1;i<=n;i++){
        if(vis[i]||i==x||f[i][x]==0){continue;}
        dfs(i);
    }
}

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&st);
        memset(num,0,sizeof(num));
        memset(f,0,sizeof(f));
        memset(vis,0,sizeof(vis));
        res=0;
        
        for(i=1;i<=n;i++){
            for(j=1;j<i;j++){
                c=getchar();
                if(c=='1'){f[i][j]=f[j][i]=0;continue;}
                if(c=='0'){f[i][j]=f[j][i]=1;num[i]++;num[j]++;res++;continue;}
                j--;
            }
        }
        for(i=1;i<=n;i++){
            if(vis[i]||!num[i]){continue;}
            it1=it2=tmp=0;
            dfs(i);
            if(it2>2){puts("-1");goto aaa;}
            if(!it1){res+=2;}
            if(it2==2){
                if(!it1||(num[st]&1)==0){puts("-1");goto aaa;}
            }
        }
        printf("%d\n",res);
        aaa:;
    }
}