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

const int N = 1000 + 9;

char G[N][N];

int deg[N];

vector<int> vc[N];

template<int N> struct Disjoint_Set_Union {
    int p[N], sz[N];
    void init(int n) { for (int i = 0; i <= n; ++i) { p[i] = i; sz[i] = 1; } }
    int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
    bool funion(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (sz[px] < sz[py]) swap(px, py);
        p[py] = px; sz[px] += sz[py];
        return true;
    }
};

Disjoint_Set_Union<N> dsu;

void solve() {
    int n, s;
    scanf("%d %d", &n, &s);
    for (int i = 2; i <= n; ++i) {
        scanf("%s", &G[i][1]);
    }
    dsu.init(n);
    memset(deg, 0, (n + 5) * sizeof(*deg));
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            if (G[i][j] == '0') {
                dsu.funion(i, j);
                ++deg[i];
                ++deg[j];
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        vc[i].clear();
    }
    for (int i = 1; i <= n; ++i) {
        vc[dsu.find(i)].push_back(i);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if ((int)vc[i].size() <= 1) continue;
        bool f = false;
        for (int u : vc[i]) if (u == s) f = true;
        if (f) {
            int cnt1 = 0, sum = 0;
            for (int u : vc[i]) {
                if (deg[u] & 1) ++cnt1;
                sum += deg[u];
            }
            if (((deg[s] & 1) && cnt1 == 2) || cnt1 == 0) {
                f = true;
                ans += sum / 2;
            }
            else {
                f = false;
            }
        }
        else {
            int cnt2 = 0, sum = 0;
            for (int u : vc[i]) {
                if (~deg[u] & 1) ++cnt2;
                sum += deg[u];
            }
            if (cnt2 == (int)vc[i].size()) {
                f = true;
                ans += sum / 2 + 2;
            }
            else {
                f = false;
            }
        }
        if (!f) {
            printf("-1\n");
            return;
        }
    }
    printf("%d\n", ans);
}

int main() {
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}