#include<bits/stdc++.h>
#define N 1005
using namespace std;
int n,st,ans;
bool odd[N],mark[N];
char str[N][N];
inline void Rd(int &res){
    char c;res=0;
    while(c=getchar(),c<48);
    do res=(res<<3)+(res<<1)+(c^48);
    while(c=getchar(),c>47);
    return;
}
inline bool check(){
    int cnt=0;
    for(int i=1;i<=n;i++){
        cnt+=odd[i];
        if(cnt>2)return false;
    }
    if(cnt==2&&!odd[st])return false;
    return true;
}
int blk;
bool key;
void dfs(int x){
    mark[x]=1;blk++;
    if(x==st)key=1;
    for(int i=1;i<x;i++)if(!mark[i]&&str[x][i]=='0')dfs(i);
    for(int i=x+1;i<=n;i++)if(!mark[i]&&str[i][x]=='0')dfs(i);
}
void init(){
    ans=0;
    memset(odd,0,sizeof(odd));
    memset(mark,0,sizeof(mark));
}
int main(){
//    freopen("data.txt","r",stdin);
    int T;
    Rd(T);
    while(T--){
        Rd(n);Rd(st);
        for(int i=2;i<=n;i++)scanf("%s",str[i]+1);
        init();
        for(int i=2;i<=n;i++){
            for(int j=1;j<i;j++){
                if(str[i][j]=='0')odd[i]^=1,odd[j]^=1,ans++;
            }
        }
        if(!check()){puts("-1");continue;}
        for(int i=1;i<=n;i++)if(!mark[i]){
            blk=0;key=0;
            dfs(i);
            if(blk>1||key)ans+=2,key=0;
        }
        ans-=2;
        printf("%d\n",ans);
    }
    return 0;
}