#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
const int N = 5e5 + 4;
int f[N],d[N],dis[N],su[N];
bool qw[N];
int find(int u)
{
    if(u!=f[u])return f[u]=find(f[u]);
    return f[u]; 
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,s;
        char c[1100];
        scanf("%d%d",&n,&s);
        for(int i=1;i<=n;i++)f[i]=i,d[i]=0,dis[i]=0,su[i]=0,qw[i]=1;
        for(int i=2;i<=n;i++)
        {
            scanf("%s",c+1);
            for(int j=1;c[j];j++)
                if(c[j]=='0')
                {
                    int l=find(i),r=find(j);
                    if(l!=r)su[r]+=su[l];
                    su[r]++;
                    f[l]=r;d[i]++;d[j]++;
                }
        }
        for(int i=1;i<=n;i++)dis[find(i)]+=(d[i]&1);
        bool flag=1;
        int x=0;
        for(int i=1;i<=n;i++)
            if(dis[find(i)]>2||dis[find(i)]==1)flag=0;
            else if(dis[find(i)]==2&&qw[find(i)])x++,qw[find(i)]=0;
        if(x==1&&d[s]%2==0)flag=0;
        if(x>1)flag=0;
        ll ans=-1;
        if(flag)
        {
            ans=su[find(s)]?-2:0;
            for(int i=1;i<=n;i++)
                if(su[find(i)])ans+=su[find(i)]+2,su[find(i)]=0;
        }
        cout<<ans<<endl;
    }
    return 0;
}