#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define mod 998244353
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
using namespace std;
const int maxn = 1005;
int fa[maxn];
int gfa(int a) {
    if (fa[a] == a) return a;
    return fa[a] = gfa(fa[a]);
}
int fl[maxn][maxn];
int hv[maxn];
char inp[maxn];
int d[maxn];
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, s;
        cin >> n >> s;
        for (int i = 1; i <= n; i++) d[i] = 0, fa[i] = i, hv[i] = 0;
        hv[s] = 1;
        int ans = 0; 
        for (int i = 2; i <= n; i++) {
            scanf("%s", inp + 1);
            for (int j = 1; j < i; j++) {
                fl[i][j] = fl[j][i] = inp[j] - '0';
                if (fl[i][j] == 0) {
                    ans += 1;
                    d[i] ^= 1, d[j] ^= 1;
                    fa[gfa(i)] = gfa(j);
                    hv[i] = hv[j] = 1;
                }
            }
        }
        int t = 0;
        for (int i = 1; i <= n; i++)
            t += (d[i] == 1);
        t -= (d[s] == 1);
        if (t >= 2) cout << -1 << endl;
        else {
            for (int i = 1; i <= n; i++)
                if (hv[i] && fa[i] == i) ans += 2;
            ans -= 2;
            cout << ans << endl;
        }
    }
    return 0;
}