#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define X first
#define Y second
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rep0(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define fore(i,a) for(int i=0;i<a.size();++i)
inline ll rd()
{
    char c=getchar();ll x=0,w=1;
    while(!isdigit(c)&&c!='-')c=getchar();
    if(c=='-')w=-1,c=getchar();
    while(isdigit(c))x=x*10+c-48,c=getchar();
    return x*w;
}
int n,s,a[1005][1005],d[1005],f[1005];
char ss[1005];
int fnd(int x){return f[x]==x?x:f[x]=fnd(f[x]);}
inline int qry(int x)
{
    vector<int>V(0);
    rep(i,1,n)if(f[i]==f[x])V.push_back(i);
    if(d[x]&1)
    {
        int s=0;
        fore(i,V)if(d[V[i]]&1)s++;
        if(s==2)return 1;
    }
    else
    {
        bool ff=1;
        fore(i,V)if(d[V[i]]&1){ff=0;break;}
        if(ff)return 2;
    }
    return 0;
}
int main()
{
    int T=rd();
    while(T--)
    {
        n=rd();s=rd();int ans=0;
        rep(i,1,n)d[i]=0,f[i]=i;
        rep(i,2,n)
        {
            scanf("%s",ss+1);
            rep(j,1,i-1)if(ss[j]=='0')
            {
                d[i]++;d[j]++;ans++;
                int u=fnd(i),v=fnd(j);
                if(u!=v)f[u]=v;
            }
        }
        rep(i,1,n)f[i]=fnd(i);
        int ff=1;
        rep(i,1,n)if(f[i]==i)
        {
            if(!d[i])continue;
            int t=qry(i==f[s]?s:i);
            if(!t){ff=0;break;}
            if(i!=f[s])
            {
                if(t==2)ans+=2;
                else {ff=0;break;}
            }
        }
        printf("%d\n",ff?ans:-1);
    }
    return 0;
}