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

char buf[1010];
int G[1010][1010];
int deg[1010];
int vis[1010];
int n, sz, s, has;

void dfs(int x) {
    vis[x] = 1, sz++, has |= x == s;
    for (int i = 0; i < n; i++) {
        if (vis[i] || !G[x][i]) continue;
        dfs(i);
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &s), s--;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                G[i][j] = 0;
            }
            deg[i] = 0;
        }
        for (int i = 1; i < n; i++) {
            scanf("%s", buf);
            for (int j = 0; j < i; j++) {
                G[i][j] = G[j][i] = buf[j] == '0';
                deg[i] += G[i][j], deg[j] += G[i][j];
            }
        }
        int tot = 0;
        for (int i = 0; i < n; i++) {
            if (deg[i] & 1) tot++;
        }
        if (tot == 1 || tot > 2 || tot == 2 && deg[s] % 2 == 0) {
            printf("-1\n");
            continue;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                ans += G[i][j];
            }
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            vis[i] = 0;
        }
        for (int i = 0; i < n; i++) {
            if (vis[i]) continue;
            sz = 0, has = 0, dfs(i);
            cnt += sz > 1 && !has;
        }
        ans += cnt * 2;
        printf("%d\n", ans);
    }
    return 0;
}