#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _for(i,a,b) for(register int (i)=(a);(i)<=(b);(i)++)
#define For(i,a,b) for(register int (i)=(a);(i)>=(b);(i)--)
#define INF 0x7fffffff
#define il inline
#define rg register
const int N=1e3+5;
int n,m,check[N][N],x,ans,tot,s,v[N],y,flag,qwq[N];
char ch[N];
queue<int>q;
int main(){
    int T;
    scanf("%d",&T);
    while(T--) {
        tot=0;
        scanf("%d%d",&n,&s);
        _for(i,2,n){
            scanf("%s",ch);
            _for(j,1,i-1){
                check[i][j]=check[j][i]=(ch[j-1]^48);
                if(check[i][j]==0) tot++;
            }
        }
        if(!tot){ puts("0"); continue; }
        int owo;
        for(owo=1; owo<=n; ++owo) if(owo!=s and !check[owo][s]) break;
        if(owo==n+1) tot+=2;
        ans=0;
        _for(i,1,n){
            flag=0;
            _for(j,1,n) if(i!=j and !check[i][j]) flag=!flag;
            if(flag) ans++;
            if(i==s) x=flag;
        }
        if(ans>=3 or (ans==2 and !x)){ puts("-1"); continue; }
        tot-=2;
        _for(i,1,n)
            _for(j,1,n) if(i!=j and !check[i][j]){
                q.push(i), q.push(j), qwq[i]=1, qwq[j]=1, v[1]=i, v[2]=j, v[0]=2;
                check[i][j]=check[j][i]=1;
                while(q.size()){
                    y=q.front(); q.pop();
                    _for(k,1,n) if(y!=k and !check[y][k] and !qwq[k]) check[y][k]=check[k][y]=1,q.push(k),qwq[k]=1,v[0]++,v[v[0]]=k;
                }
                tot+=2;
                _for(k,1,v[0]){
                    _for(l,1,v[0]) if(l!=k) check[v[k]][v[l]]=check[v[l]][v[k]]=1;
                    qwq[v[k]]=0;
                }
            }
        printf("%d\n",tot);
    }
    return 0;
}