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

void debug_out(){
    cerr << endl;
}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
    cerr << ' ' << H;
    debug_out(T...);
}
#ifdef local
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 55
#endif

const int N = 1005;
char S[N];
int du[N], f[N], sz[N];
int find(int x){
    return x == f[x]? x: f[x] = find(f[x]);
}
int main() {
#ifdef local
    freopen("../in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        int n, s, tot = 0;
        cin >> n >> s;
        for(int i = 1; i <= n; i++) f[i] = i, du[i] = 0, sz[i] = 0;
        for(int i = 1; i < n; i++){
            cin >> S + 1;
            for(int j = 1; j <= i; j++){
                if(S[j] == '0'){
                    du[j]++, du[i + 1]++;
                    tot++;
                    if(find(j) != find(i + 1)) f[find(j)] = find(i + 1);
                }
            }
        }
        int cnt = 0;
        for(int i = 1; i <= n; i++){
            if(du[i] % 2 == 1) cnt++;
        }
        if(cnt > 2 || (cnt == 2 && du[s] % 2 == 0)) cout << -1 << '\n';
        else{
            for(int i = 1; i <= n; i++) sz[find(i)]++;
            int num = 0;
            for(int i = 1; i <= n; i++){
                if(i == find(i)) num += (sz[i] > 1);
            }
            if(sz[find(s)] == 1) num++;
            cout << tot + (num - 1) * 2 << '\n';
        }
    }
    return 0;
}