#include<bits/stdc++.h>
using namespace std;

int T, n, st, G[1111][1111], deg[1111];
char s[1111];

int vis[1111];

void dfs(int x){
    vis[x]=1;
    for (int i=1;i<=n;++i)
        if (G[x][i]&&!vis[i])
            dfs(i);
}

int main(){
    for (cin>>T;T--;){
        cin>>n>>st;
        memset(G,0,sizeof G);
        memset(deg,0,sizeof deg);
        int tot=0;
        for (int i=2;i<=n;++i){
            scanf("%s",s+1);
            for (int j=1;j<i;++j)
                if (s[j]=='0'){
                    G[i][j]=G[j][i]=1;
                    ++deg[i]; ++deg[j]; ++tot;
                }
        }
        set<int>S;
        for (int i=1;i<=n;++i)
            if (deg[i]&1) S.insert(i);
        if (S.size()>2){
            puts("-1"); continue;
        }
        if (S.size()==2&&!S.count(st)){
            puts("-1"); continue;
        }
        if (!tot){
            puts("0"); continue;
        }
        memset(vis,0,sizeof vis);
        int blocks=0;
        for (int i=1;i<=n;++i)
            if (!vis[i]&&deg[i]){
                ++blocks; dfs(i);
            }
        int ans=tot+(blocks-1)*2+((deg[st]==0)? 2: 0);
        cout<<ans<<endl;
    }
}