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

typedef long long LL;

const int MAXN = 1005;

int n, st;
int deg[MAXN];
int p[MAXN];
int num[MAXN][2];
char s[MAXN];

int f(int x) {
    return p[x] == x?x:p[x] = f(p[x]);
}

void solve() {
    int ans = 0;
    scanf("%d%d", &n, &st);
    for(int i = 1; i <= n; i++) {
        p[i] = i;
        num[i][0] = num[i][1] = 0;
        deg[i] = 0;
    }
    for(int i = 2; i <= n; i++) {
        scanf("%s", s+1);
        for(int j = 1; j < i; j++) {
            if(s[j] == '0') {
                deg[i] ++;
                deg[j] ++;
                p[f(i)] = f(j);
                ans++;
            }
        }
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        int x = f(i);
        if(x == i && (deg[i] > 0|| st == i)) cnt++;
        num[x][deg[i]&1] ++;
    }
    if(cnt > 0) ans += (cnt - 1) * 2;
    //for(int i = 1; i <= n; i++) {
    //    printf("%d %d\n", num[i][0], num[i][1]);
    //}
    for(int i = 1; i <= n; i++) {
        int x = f(i);
        if(x != i) continue;
        if(num[i][1]) {
            if(num[i][1] != 2) {
                puts("-1");
                return;
            }
            if(f(st) != i || deg[st] % 2 == 0) {
                puts("-1");
                return;
            }
        }
    }
    printf("%d\n", ans);
}

int main() {
    int T;
    scanf("%d", &T);
    for(int i = 1; i <= T; i++) solve();
    return 0;
}