#include<bits/stdc++.h>
using namespace std;
int n,S,T,tot,totg;
int a[1005][1005],cnt[1005],vis[1005];
char s[1005];
void init()
{
    tot=0,totg=0;
    for(int i=1;i<=n;i++) cnt[i]=vis[i]=0;
}
void dfs(int x)
{
    vis[x]=1;
    for(int i=1;i<=n;i++) if(!vis[i]&&!a[x][i]) dfs(i);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&S);
        init();
        for(int i=2;i<=n;i++)
        {
            scanf("%s",s+1);
            for(int j=1;j<=i-1;j++) 
            {
                a[i][j]=a[j][i]=s[j]-'0';
                if(a[i][j]==0) cnt[i]++,cnt[j]++,tot++;
            }
        }
        int flag=0;
        for(int i=1;i<=n;i++) if((cnt[i]||i==S)&&!vis[i]) dfs(i),totg++;
        for(int i=1;i<=n;i++) flag+=(cnt[i]&1);
        if(flag>2||(flag==2&&!(cnt[S]&1))) puts("-1");
        else printf("%d\n",tot+(totg-1)*2);
    }
    return 0;
}