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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        int n, s;
        cin >> n >> s;
        s--;
        vector<vector<int>> graph(n);
        vector<int> deg(n);
        for (int i = 1; i < n; i++) {
            string s;
            cin >> s;
            for (int j = 0; j < (int)s.size(); j++) {
                if (s[j] == '0') {
                    graph[j].push_back(i);
                    graph[i].push_back(j);
                    deg[i]++; deg[j]++;
                }
            }
        }
        auto solve = [&]() {
            auto is_eulerian = [&](vector<int> path) {
                int odd = 0, edges = 0;
                for (int &u : path) {
                    if (deg[u] % 2) {
                        odd++;
                    }
                    edges += deg[u];
                }
                if (odd == 0) {
                    return make_pair(0, edges / 2);
                } else if (odd == 2) {
                    return make_pair(1, edges / 2);
                }
                return make_pair(-1, -1);
            };
            vector<bool> vis(n);
            auto get_path = [&](int s) {
                vector<int> path;
                function<void(int)> dfs = [&](int u) {
                    path.push_back(u);
                    vis[u] = true;
                    for (int &v : graph[u]) {
                        if (vis[v]) {
                            continue;
                        }
                        dfs(v);
                    }
                };
                dfs(s);
                return path;
            };
            if (n == 1) {
                return 0;
            }
            vector<int> fi, se;
            for (int i = 0; i < n; i++) {
                if (vis[i]) {
                    continue;
                }
                pair<int, int> res = is_eulerian(get_path(i));
                if (res.first == 0) {
                    if (res.second != 0) 
                    fi.push_back(res.second);
                } else if (res.first == 1) {
                    if (res.second != 0)
                    se.push_back(res.second);
                } else {
                    return -1;
                }
            }
            int sum = accumulate(fi.begin(), fi.end(), 0);
            if ((int)se.size() > 1) {
                return -1;
            } else if ((int)se.size() == 1) {
                if (deg[s] % 2) {
                    return se[0] + sum + (int)fi.size() * 2;
                } else {
                    return -1;
                }
            } else {
                if (deg[s]) {
                    return sum + ((int)fi.size() - 1) * 2;
                } else {
                    return sum + (int)fi.size() * 2;
                }
            }
        };
        cout << solve() << '\n';
    }
    return 0;
}