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

int n, s, edges;
int d[maxn], p[maxn], sz[maxn];
bool isodd[maxn];

int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }

int main()
{
    int T; cin >> T;
    char ch;
    while (T -- )
    {
        cin >> n >> s;
        edges = 0;
        for (int i = 1; i <= n; i ++ ) p[i] = i, isodd[i] = 0, d[i] = 0, sz[i] = 1;
        for (int i = 2; i <= n; i ++ )
            for (int j = 1; j < i; j ++ )
            {
                cin >> ch;
                if (ch == '0')
                {
                    d[i] ++, d[j] ++, edges ++ ;
                    int a = find(i), b = find(j);
                    if (a != b) p[a] = b, sz[b] += sz[a];
                }
            }
        
        int cnt = 0;
        for (int i = 1; i <= n; i ++ ) if (d[i] & 1) cnt ++, isodd[i] = true;
        if (cnt > 2 || (cnt == 2 && !isodd[s])) { puts("-1"); continue; }
        
        cnt = 0;
        for (int i = 1; i <= n; i ++ ) if (find(i) == i && sz[i] != 1) cnt ++ ;
        if (find(s) == s && sz[s] == 1) cnt ++ ;
        
        cout << edges + 2 * (cnt - 1) << endl;
    }
    
    return 0;
}