#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1e3+10,P=998244353;
long long qpow(long long p,int q){
    long long res=1;
    while(q){
        if(q&1)res=res*p%P;
        q>>=1;
        p=p*p%P;
    }
    return res;
}
int n,s;
char str[maxn];
vector<int>T[maxn];
bool vis[maxn];
int cnt[maxn];
int id,Q[maxn];
void dfs(int f,int x){
    Q[++id]=x;
    vis[x]=1;
    for(int i=0;i<T[x].size();i++){
        int y=T[x][i];
        if(vis[y])continue;
        dfs(x,y);
    }
}
int main(){
//    freopen("data.in","r",stdin);
//    freopen("std.out","w",stdout);
    int QuQ;cin>>QuQ;
    while(QuQ--){
        scanf("%d%d",&n,&s);
        for(int i=1;i<=n;i++){
            T[i].clear();
//            T[i].push_back(i);
            vis[i]=0;
            cnt[i]=0;
        }
        for(int i=2;i<=n;i++){
            scanf("%s",str+1);
            for(int j=1;j<i;j++){
                if(str[j]=='0'){
                    T[i].push_back(j);
                    T[j].push_back(i);
                    cnt[i]++;
                    cnt[j]++;
                }
            }
        }
        bool flag=1;
        int ans=0;
        for(int i=1;i<=n&&flag;i++){
            if(!vis[i]){
                id=0;
                dfs(0,i);
                if(id==1){
                    continue;
                }
                int tmp[5],ID=0;
                bool isok=0;
                int sum=0;
                for(int j=1;j<=id&&flag;j++){
                    int x=Q[j];
//                    debug(x);
                    sum+=cnt[x];
                    if(x==s)isok=1;
                    
                    if(cnt[x]%2==1){
                        ID++;
                        if(ID>=3)flag=0;
                        tmp[ID]=x;
                    }
                }
//                debug(ans);
//                debug(sum);
//                debug(id);
//                debug(ID);
                if(ID!=0&&ID!=2)flag=0;
                else {
                    if(ID==0){
                        if(isok)ans+=sum/2;
                        else ans+=sum/2+2;
                    }else if(ID==2){
//                debug(ID);
//                puts("");
                        if(isok){
                            if(tmp[1]==s||tmp[2]==s)
                                ans+=sum/2;
                            else flag=0;
                        }else flag=0;
                    }
                }
            }
        }
        if(flag)cout<<ans<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}