#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstring>
#include <queue>
#include <vector>
#include <iostream>
#define LL long long
#define LD long double
#define MAXN 1005
#define MAXM
#define P
#define MP make_pair
#define PB push_back
#define INF 0x3f3f3f3f
#define dbg(a...) fprintf(stderr, a)
using namespace std;

int T, n, s, vis[MAXN], num[MAXN];
char mp[MAXN][MAXN];

void dfs(int x)
{
    vis[x]=1;
    for(int i=1; i<=n; ++i)
        if(mp[x][i]=='0' && !vis[i]) dfs(i); 
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        int ans=0;
        scanf("%d%d", &n, &s);
        for(int i=1; i<=n; ++i) num[i]=vis[i]=0;
        for(int i=2; i<=n; ++i) scanf("%s", mp[i]+1);
        for(int i=1; i<=n; i++) {
            mp[i][i]=1;
            for(int j=i+1; j<=n; ++j) {
                mp[i][j]=mp[j][i];
                if(mp[i][j]=='0') ans++;
            }
        }
        int cnt=0, flag=1;
        for(int i=1; i<=n; ++i) {
            num[i]=0;
            for(int j=1; j<=n; ++j)
                if(mp[i][j]=='0') num[i]++;
            if(num[i]&1) cnt++;
        }
        if(cnt>2 || cnt==1) flag=0;
        if(cnt==2 && num[s]%2==0) flag=0;
        if(!flag) {
            printf("-1\n");
            continue;
        }
        dfs(s);
        for(int i=1; i<=n; ++i)
            if(!vis[i] && num[i]>0) dfs(i), ans+=2;
        printf("%d\n", ans);
    }
    return 0;
}
/*

0
11
111
1111
*/