#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define int long long
using namespace std;
void fileio(const string &s)
{
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}
const int INF=4e18;
inline int read()
{
    int x=0;
    bool flag=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            flag=0;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return (flag?x:~(x-1));
}
int t,n,s,tot,fa[1001],num[1001],pop[1001];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void solve()
{
    n=read();
    s=read();
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        num[i]=0;
        pop[i]=0;
    }
    tot=0;
    for(int i=2;i<=n;i++)
    {
        string ss;
        cin>>ss;
        for(int l=1;l<i;l++)
            if(ss[l-1]=='0')
            {
                fa[find(i)]=find(l);
                num[i]++;
                num[l]++;
                tot++;
            }
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
        if(num[i]&1)
            cnt++;
    if(cnt>2)
    {
        puts("-1");
        return ;
    }
    if(cnt==2&&num[s]%2==0)
    {
        puts("-1");
        return ;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        pop[find(i)]++;
    for(int i=1;i<=n;i++)
        if(find(i)==i)
            if(s==i||pop[i]!=1)
                ans++;
    cout<<(ans-1)*2+tot<<endl;
} 
signed main()
{
    t=read();
    while(t--)
        solve();
    return 0;
}