// #pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>

using namespace std;

#define rep(i, l, r) for(int i=l; i<=r; i++)
#define dow(i, l, r) for(int i=l; i>=r; i--)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define clr(x, c) memset(x,c,sizeof(x))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;

inline int read() {
    int x=0,f=0; char ch=getchar();
    while (ch<'0' || '9'<ch) f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9') x=x*10+ch-'0', ch=getchar();
    return f?-x:x;
}

// ====================================================== 全局数据

// #define Q 1000000007

// ====================================================== 模板代码

// =========================== 加边

// #define travel(x) for(edge *p=fir[x]; p; p=p->n)
// struct edge{int y; edge *n;} e[maxm], *fir[maxn], *pt=e;
// void AddE(int x, int y){pt->y=y, pt->n=fir[x], fir[x]=pt++;}

// =========================== 快速幂

// inline int pow(int x, int t) {
//     int g = 1;
//     while (t) {
//         if (t&1) g = 1LL*g*x%Q;
//         x = 1LL*x*x%Q;
//         t >>= 1;
//     }
//     return g;
// }

// ====================================================== 主程序

#define maxn 1009

int h[maxn];
int head(int a) {return h[a]=((h[a]==a)?a:head(h[a]));}
inline void join(int a, int b) {h[head(a)] = head(b);}

int c[maxn];
bool b[maxn][maxn];
char str[maxn];

int main() {
    int T = read(); while (T--) {
        int n = read(), s = read();
        rep(i, 2, n) {
            scanf("%s", str);
            rep(j, 1, i-1) b[i][j] = (str[j-1] == '0'), b[j][i] = (str[j-1] == '0');
        }
        rep(i, 1, n) c[i] = 0, h[i] = i;
        rep(i, 1, n) rep(j, 1, n) if (i != j && b[i][j]) c[i] ^= 1, join(i, j);
        int num = 0;
        rep(i, 1, n) if (c[i]) num += 1;
        if (c[s]) num -= 2;
        if (num != 0) {
            puts("-1");
            continue;
        }
        num = -1;
        rep(i, 1, n) c[i] = 0;
        rep(i, 1, n) c[head(i)]++;
        rep(i, 1, n) if (c[i] > 1) num++;
        if (c[s] == 1) num++;
        num *= 2;
        rep(i, 1, n) rep(j, 1, i-1) if (b[i][j]) num += 1;
        printf("%d\n", num);
    }
    return 0;
}