#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
#define mem(x,v) memset(x,v,sizeof(x))
#define fi first
#define se second
#define lowbit(x) ((x)&-(x))
#define debug(x) cout << #x " = " << x << endl;
namespace IO{
    const int L = 1 << 15;
    char c,st[66];int tp=0,f;
    #define gc getchar
    #define pc putchar
    inline ll read(){
        ll x=0;f=1,c=gc();
        for(;!isdigit(c);c=gc())if(c=='-')f=-1;
        for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c&15);
        return x*f;
    }
    void write(ll x){
        if(!x) pc('0');if(x<0) pc('-'),x=-x;
        while(x) st[++tp]=x%10+'0',x/=10;
        while(tp) pc(st[tp--]);
    }
    void wri(ll x){write(x);pc(' ');}
    void writeln(ll x){write(x);pc('\n');}
}
using IO::read;
using IO::writeln;
using IO::write;
using IO::wri;
inline void gg(string s){cout << s << endl;exit(0);}
inline void gg(ll x){writeln(x);exit(0);}
const int mod = 998244353;
inline int qpow(int a,int b){
    int ans=1;
    for(;b;b>>=1,a=1ll*a*a%mod)
        if(b&1) ans=1ll*ans*a%mod;
    return ans;
}
bool a[1005][1005];
bool vis[1005];int deg[1005],n,s;
pair<int,int> dfs(int i){
    int c1=deg[i]&1,c2=deg[i];
    vis[i] = true;
    Rep(j,1,n) if(!vis[j] && a[i][j]==0){
//        printf("%d->%d\n",i,j);
        pii tmp = dfs(j);
        c1 += tmp.fi;
        c2 += tmp.se;
    }return make_pair(c1,c2);
}
pii w;
void solve(){
    n = read(),s = read();
    Rep(i,1,n) deg[i] = 0;
    Rep(i,2,n){
        Rep(j,1,i-1){
            char ch = getchar();
            while(ch!='0'&&ch!='1') ch=getchar();
            a[i][j]=a[j][i]=ch-'0';
            if(a[i][j]==0) deg[i]++,deg[j]++;
        }
    }
//    Rep(i,1,n) printf("%d ",deg[i]);puts("");
    Rep(i,1,n) vis[i] = false;
    w = dfs(s);w.se/=2;
//    puts("~~~~~~~~~~~");
//    wri(w.fi),writeln(w.se);
//    puts("~~~~~~~~~~~");
    if((w.fi!=2&&w.fi!=0)){
        puts("-1");return ;
    }
    if(w.fi==2 && deg[s]%2==0){
        puts("-1");return ;
    }
    int ans = w.se;
    Rep(i,1,n) if(!vis[i]){
//        printf("[%d]\n",i);
        w = dfs(i);w.se/=2;
//        printf("{%d %d}\n",w.fi,w.se);
        if(w.fi!=0){
            puts("-1");return ;
        }
        if(w.se) ans += w.se + 2;
    }writeln(ans);
}

int main(){
    int T = read();
    while(T--){
        solve();
    }
}