#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
//#define int long long
using namespace __gnu_pbds;
using namespace std;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int n,s,deg[1010];
bool vis[1010][1010],ok[1010],used[1010];

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

signed main()
{
    ios::sync_with_stdio(false);
    int t;cin>>t;
    while(t--){
        cin>>n>>s;
        for(int i=1;i<=n;i++) deg[i]=0,ok[i]=0,used[i]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) vis[i][j]=vis[j][i]=0;
        }
        int tot=0;
        for(int i=2;i<=n;i++){
            for(int j=1;j<i;j++){
                char ch;cin>>ch; 
                if(ch=='0'){
                    deg[j]++;deg[i]++;vis[i][j]=vis[j][i]=1;tot++;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) if(vis[i][j]) ok[i]=1;
            if(i==s) ok[i]=1;
        }
        int cnt=0;
        for(int i=1;i<=n;i++) if(ok[i]&&!used[i]){
            dfs(i);cnt++;
        }
        int all=0;
        for(int i=1;i<=n;i++) if(deg[i]%2==1) all++;
        if(all>=4){
            cout<<-1<<'\n';
            continue;
        }
        if(all==2&&deg[s]%2==0){
            cout<<-1<<'\n';
            continue;
        }
        cout<<tot+2*(cnt-1)<<'\n';
    }
    return 0;
}