#include<bits/stdc++.h>
#define LL long long
#define M 1005
using namespace std;
int n,s;
char edge[M];
bool clo[M][M];
int bel[M],bcnt,mark[M];
vector<int>G[M],poi,jid;
void dfs(int v,int b){
    bel[v]=b;poi.push_back(v);
    for(int u:G[v])if(!bel[u])dfs(u,b);
}
int main(){
    for(int _=(scanf("%d",&_),_);_;_--){
        scanf("%d%d",&n,&s);
        bcnt=0;int ans=0;jid.clear();
        for(int i=1;i<=n;i++)bel[i]=mark[i]=0,G[i].clear();
        for(int i=2;i<=n;i++){
            scanf("%s",edge+1);
            for(int j=1;j<i;j++)if(edge[j]=='0')
                G[i].push_back(j),G[j].push_back(i),ans++;
        }
        if(!ans){puts("0");continue;}
        int flg=0,cnt=0,hav=0;
        for(int i=1;i<=n&&flg<2;i++)if(!bel[i]){
            poi.clear();
            dfs(i,++bcnt);
            if(poi.size()>1){
                int c=0,f=0;
                for(int v:poi){
                    mark[v]=1;
                    if(G[v].size()&1)
                        c++,jid.push_back(v);
                }
                if(c>2)flg=2;
                if(c==2)flg++;
                cnt++;
            }
        }
        if(flg>=2)puts("-1");
        else if(!flg)printf("%d\n",ans+max(cnt-1,0)*2+(mark[s]==0)*2);
        else if(jid[0]!=s&&jid[1]!=s)puts("-1");
        else printf("%d\n",ans+max(cnt-1,0)*2);
    }
    return 0;
}