#include <stdio.h>
#include <algorithm>

using namespace std;

struct node {
    int v;
    node *next;
} pool[1200000] , *g[1200];
int top;
int n , s;
char z[1200];
int d[1200];
int vis[1200] , color;
int cnt[1200] , tot;
void clear () {
    int i;
    for ( i = 1 ; i <= n ; i++ ) {
        g[i] = NULL;
        d[i] = 0;
        vis[i] = 0;
        cnt[i] = 0;
    }
    tot = 0;
    top = color = 0;
}
void add ( int u , int v ) {
    node *tmp = &pool[++top];
    tmp -> v = v; tmp -> next = g[u]; g[u] = tmp;
}
void dfs ( int i , int from ) {
    if ( vis[i] ) return ;
    vis[i] = color;
    cnt[color]++;
    for ( node *j = g[i] ; j ; j = j -> next ) if ( j -> v != from ) {
        dfs ( j -> v , i );
    }
}
int bad () {
    printf ( "-1\n" );
    return 0;
}
int work () {
    int i , j , e , odd;
    scanf ( "%d%d" , &n , &s );
    e = 0;
    for ( i = 2 ; i <= n ; i++ ) {
        scanf ( "%s" , z + 1 );
        for ( j = 1 ; j <= i - 1 ; j++ ) {
            if ( z[j] == '0' ) {
                d[i]++;
                d[j]++;
                add ( i , j );
                add ( j , i );
                e++;
            }
        }
    }
    for ( i = 1 ; i <= n ; i++ ) {
        if ( vis[i] == 0 ) {
            color++;
            dfs ( i , -1 );
        }
    }
    odd = 0;
    for ( i = 1 ; i <= n ; i++ ) {
        if ( vis[i] == vis[s] ) {
            if ( d[i] % 2 == 1 ) odd++;
        }
        else {
            if ( d[i] % 2 == 1 ) return bad ();
        }
    }
    for ( i = 1 ; i <= color ; i++ ) {
        if ( i != vis[s] ) {
            if ( cnt[i] > 1 ) tot++;
        }
    }
    if ( odd > 2 || (odd==2&&d[s]%2==0) ) return bad ();
    printf ( "%d\n" , e + (tot) * 2 );
    return 0;
}
int main () {
    int t;
    scanf ( "%d" , &t );
    while ( t-- ) {
        work ();
        clear ();
    }
    return 0;
}