#include<iostream>
#include<queue>
#include<string.h>
#include<algorithm>
#include<string>
#include<iomanip>
#include<vector>
#include<set>
#include<cmath>
#include<map>
#include<list>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
const int maxn = 1e3 + 7;
const int INF = (1 << 31) - 1;
const int mod = 998244353;
int du[maxn];
vector<int> e[maxn];
int cnt = 0;
bool vis[maxn];
void dfs(int from) {
    vis[from] = 1;
    if (du[from] & 1)cnt++;
    for (int& to : e[from]) {
        if (!vis[to])dfs(to);
    }
}
void work() {
    int n, s; cin >> n >> s;
    int tot = 0;
    memset(du, 0, sizeof(int) * (n + 1));
    memset(vis, 0, sizeof(bool) * (n + 1));
    for (int i = 1; i <= n; ++i)e[i].clear();
    for (int i = 1; i < n; ++i) {
        string s; cin >> s;
        for (int j = 0; j < s.size(); ++j) {
            if (s[j] == '0')du[j + 1]++, du[i + 1]++, tot++, e[j + 1].push_back(i + 1), e[i + 1].push_back(j + 1);
        }
    }
    if (tot == 0) {
        cout << 0 << '\n'; return;
    }
    int part = 0;
    cnt = 0;
    dfs(s);
    if (cnt != 0 && cnt != 2) {
        cout << -1 << '\n';
        return;
    }
    if (cnt == 2 && du[s] % 2 == 0) {
        cout << -1 << '\n'; return;
    }
    part++;
    for (int i = 1; i <= n; ++i) {
        if (vis[i])continue;
        cnt = 0; dfs(i);
        if (du[i] != 0)part++;
        if (cnt != 0) {
            cout << -1 << '\n'; return;
        }
    }
    
    cout << tot + (part - 1) * 2 << '\n';
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    for (int i = 1; i <= T; ++i) {
        //        cout << "Case #" << i << ": ";
        work();
    }
}