#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e3+10;
char s[N];
bool e[N][N];
int in[N];
bool vis[N];
int n;

void dfs(int u, vector<int>& vec) {
    if (vis[u]) return ;
    vis[u] = 1;
    vec.push_back(u);
    for (int i = 1; i <= n; i++) {
        if (e[u][i] && !vis[i]) {
            dfs(i, vec);
        }
    }
}

void solve() {
    int root;
    scanf("%d%d", &n, &root);

    for (int i = 1; i <= n; i++) {
        in[i] = 0;
        vis[i] = 0;
        for (int j = 1; j <= n; j++)
            e[i][j] = 0;
    }

    int es = 0;
    for (int i = 2; i <= n; i++) {
        scanf("%s", s+1);
        for (int j = 1; j < i; j++) {
            if (s[j] == '0') {
                e[i][j] = e[j][i] = 1;
                in[i]++, in[j]++;
                es++;
            }
        }
    }
    if (es == 0) {
        printf("0\n");
        return ;
    }

    int cir = 0, link = 0;
    int incir = 0, inlink = 0;
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) continue;
        if (vis[i]) continue;
        vector<int> vec;
        dfs(i, vec);
        int odd = 0, even = 0;
        int curf = 0;
        for (int u : vec) {
            if (in[u]&1) {
                odd++;
                if (u == root) curf = 1;
            } else {
                even++;
                if (u == root) curf = 2;
            }
        }
        assert(odd+even);
        if (odd != 0 && odd != 2) {
            printf("-1\n");
            return ;
        }
        if (odd == 0) {
            cir++;
            if (curf) incir = 1;
        } else {
            link++;
            if (curf) inlink = 1;
        }
    }
    if (link > 1) {
        printf("-1\n");
        return ;
    }

    if (in[root] == 0) {
        if (link) {
            printf("-1\n");
            return ;
        }
        es += cir*2;
        printf("%d\n", es);
        return ;
    }

    if (link == 1) {
        if (!inlink || (in[root]%2 == 0)) {
            printf("-1\n");
            return ;
        }
    }

    es += (cir+link-1)*2;
    printf("%d\n", es);
}

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