#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define setIO(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
#define closefile fclose(stdin), fclose(stdout)
#define m_p make_pair
#define sz(x) (int)x.size()
#define see(x) cerr << x << " "
#define seeln(x) cerr << x << endl
#define out(x) cerr << #x << " = " << x << " "
#define outln(x) cerr << #x << " = " << x << endl
#define outarr(x, l, r) {cerr << #x"[" << l << " ~ " << r << "] = "; for (int _i = l; _i <= r; ++_i) cerr << x[_i] << " "; cerr << endl;}
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
template <class T> bool checkmax(T &a, T b){return a < b ? a = b, 1 : 0;}
template <class T> bool checkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
const int N = 100005;
int n, s, m;
int fa[1005];
int deg[1005], bel[1005];
char st[1905];
int gf(int x){return fa[x] == x ? x : fa[x] = gf(fa[x]);}
void unite(int x, int y)
{
    if (gf(x) != gf(y))
    {
        fa[gf(x)] = gf(y);
    }
}

void init()
{
    scanf("%d%d", &n, &s), m = 0;
    for (int i = 1; i <= n; ++i) fa[i] = i, deg[i] = 0;
    for (int i = 2; i <= n; ++i)
    {
        scanf("%s", st + 1);
        for (int j = 1; j < i; ++j) if (st[j] == '0')
        {
            unite(i, j);
            ++deg[i], ++deg[j];
            ++m;
        }
    }
}

void solve()
{
    vector<int> w;
    for (int i = 1; i <= n; ++i) if (deg[i] & 1) w.push_back(i);
    if (sz(w) % 2 == 1 || sz(w) > 2)
    {
        printf("-1\n");
        return;
    }
    if (sz(w) == 2 && deg[s] % 2 == 0)
    {
        printf("-1\n");
        return;
    }
    int o = 0, t = gf(s);
    for (int i = 1; i <= n; ++i) bel[i] = 0;
    for (int i = 1; i <= n; ++i) ++bel[gf(i)];
    for (int i = 1; i <= n; ++i) if (i != t && bel[i] > 1) ++o;
    printf("%d\n", m + o + o);
}

int main()
{
    int t; scanf("%d", &t); while (t--)
    {
        init();
        solve();
    }
    return 0;
}