#include <bits/stdc++.h>
using namespace std;
char str[1010];
int f[1010], d[1010], vis[1010];
int find(int x){
    return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int u, int v){
    int fa = find(u), fb = find(v);
    d[u]++;
    d[v]++;
    if (fa != fb){
        f[fa] = fb;
    }
}
void solve(){
    int n, s;
    cin >> n >> s;
    for (int i = 1; i <= n; i++) f[i] = i, d[i] = 0, vis[i] = 0;
    int tot = 0;
    for (int i = 2; i <= n; i++) {
        scanf("%s", str + 1);
        for (int j = 1; j < i; j++) {
            if (str[j] == '0') {
                merge(i, j);
                tot++;
            }
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if ((d[i] & 1) && (find(i) != find(s))) {
            puts("-1");
            return;
        }
        if ((d[i] & 1) && (find(i) == find(s))) cnt++;
        if (!vis[(find(i))]) {
            if (d[i] && find(i) != find(s)) tot += 2;
            vis[find(i)] = 1;
        }
    }
    if ((cnt > 2) || (cnt && !(d[s] & 1) )) {
        puts("-1");
        return;
    }
    cout << tot << endl;

    
}
int main(){
    int T;
    cin >> T;
    while (T--) solve();
}