#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define x first
#define y second
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x,T y){x<y?x=y:T();}
template <typename T> void chkmin(T &x,T y){y<x?x=y:T();}
template <typename T> void readint(T &x)
{
    x=0;int f=1;char c;
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=x*10+(c-'0');
    x*=f;
}
/*const int MOD=;
inline int dmy(int x){return x>=MOD?x-MOD:x;}
inline void inc(int &x,int y){x=dmy(x+y);}
int qmi(int x,int y)
{
    int ans=1;
    for(;y;y>>=1,x=1ll*x*x%MOD)
        if(y&1)ans=1ll*ans*x%MOD;
    return ans;
}*/
const int MAXN=1005;

int n,src;
int G[MAXN][MAXN],fa[MAXN],sz[MAXN];
char str[MAXN];
int getfa(int u){return u==fa[u]?u:fa[u]=getfa(fa[u]);}
void solve()
{
    readint(n),readint(src);
    for(int i=2;i<=n;++i)
    {
        scanf("%s",str+1);
        for(int j=1;j<i;++j)G[i][j]=G[j][i]=1^(str[j]-'0');
    }
    int cnt=0;
    for(int i=1;i<=n;++i)
    {
        int d=(i==src);
        for(int j=1;j<=n;++j)
            d^=G[i][j];
        cnt+=d;
    }
    if(cnt!=1){cout<<"-1\n";return;}
    cnt=0;
    for(int i=1;i<=n;++i)sz[i]=1,fa[i]=i;
    for(int i=1;i<=n;++i)
        for(int j=1;j<i;++j)
            if(G[i][j])
            {
                ++cnt;
                int u=getfa(i),v=getfa(j);
                if(u==v)continue;
                fa[u]=v,sz[v]+=sz[u];
            }
    int ano=0;
    for(int i=1;i<=n;++i)
        if(i==getfa(i) && (sz[i]>=2 || i==getfa(src)) )
            ++ano;
    cout<<cnt+(ano-1)*2<<'\n';
}

int main()
{
    #ifdef LOCAL
    freopen("code.in","r",stdin);
//    freopen("code.out","w",stdout);
    #endif
    int T;
    readint(T);
    while(T--)solve();
    return 0;
}