#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sc(x) scanf("%lld",&(x));
#define pb push_back
#define fi first
#define se second

#define maxn  5000000


int a,b;
int n,m,k;


int T;
int s;
signed A[1005][1004];
char g[1005];
int deg[1005];
bool vis[1004];
int ans;
void dfs(int x){
    vis[x] = 1;
    for(int i = 1; i <= n; i++){

        if(A[x][i] == 1){
            A[x][i] = 0;
            A[i][x] = 0;

            ans ++;
            if(!vis[i]){
                dfs(i);
            }
        }
    }
}
int W[1004];
signed main(){
   sc(T)
   while(T--){
    sc(n)
    sc(s)
    ans = 0;
    memset(vis,0,sizeof(vis));
    memset(deg,0,sizeof(deg));
    memset(W,0,sizeof(W));
    for(int i = 1; i <= n-1; i++){
            scanf("%s",g+1);
            for(int j = 1; j <= i; j++){
                A[i+1][j] = A[j][i+1] = ((g[j] - '0')^1);
            }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(A[i][j])deg[i] += 1;
        }

    }
    dfs(s);
    int a = 0;

    for(int i = 1; i <= n; i++){
        if(vis[i] && (deg[i]&1)){
            a++;
        }
        if(vis[i]){W[i] = 1;}
    }

    if(a != 0 && a != 2){
        cout << -1 << "\n";
        continue;
    }
    
    if(a == 2 && !(deg[s] & 1)){
        cout << -1 << "\n";
        continue;
    }

    bool f = false;
    bool flag = false;
    for(int i = 1; i <= n; i++){
        if(W[i])continue;
        f = false;
        for(int j = i+1; j <= n; j++){
            if(A[i][j]){
                f = true;
                break;
            }
        }
        if(f){
            ans += 2;
            memset(vis,0,sizeof(vis));
            dfs(i);
            for(int i = 1; i <= n; i++){
                if(vis[i] && (deg[i] &1)){
                    flag = true;
                    //break;
                }
                if(vis[i]){
                    W[i] = 1;
                }
            }

        }

        if(flag)break;
    }
    if(flag){
        cout << -1 << '\n';
        continue;
    }
    cout << ans << '\n';




   }
}