#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e3+5;
char s[M];
int tes,n,st,num,ans;
int a[M][M],dg[M],id[M];
void dfs(int x){
    id[x]=num;
    for(int y=1;y<=n;y++)if(a[x][y]&&!id[y]){
        id[y]=num;
        dfs(y);
    }
}
void solve(){
    scanf("%d%d",&n,&st);
    for(int i=2;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<i;j++)a[i][j]=a[j][i]=((s[j]-48)^1);
    }
    for(int i=1;i<=n;i++)dg[i]=id[i]=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        dg[i]+=a[i][j];
    int cnt=0;num=ans=0;
    for(int i=1;i<=n;i++)cnt+=(dg[i]&1),ans+=dg[i];
    if(cnt>2||(cnt==2&&dg[st]%2==0)){puts("-1");return;}
    for(int i=1;i<=n;i++)if(dg[i]>0&&!id[i]){++num;dfs(i);}
    if(num>0&&!id[st])++num;
    if(ans==0&&num==0)puts("0");
    else printf("%d\n",(ans>>1)+(num-1)*2);
}
int main()
{
    scanf("%d",&tes);
    while(tes--)solve();
    return 0;
}