#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N=1500,INF=1e9+7;
int read(int &n)
{
    bool q=0;n=0;char ch=' ';
    for(;ch!='-'&&(ch<'0'||ch>'9');ch=getchar());
    if(ch=='-')ch=getchar(),q=1;
    for(;ch>='0'&&ch<='9';ch=getchar())n=(n<<3)+(n<<1)+ch-48;
    return q?n=-n:n;
}
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(seed);  // 大随机数
int RD(int q){return rand_num()%q;}


int n,m,ans;
int z[N];
int B[N][N],Bv[N];
int cnt;
void dfs(int q)
{
    if(Bv[q]&1)++cnt;
    z[q]=1;
    fo(i,1,n)if(!z[i]&& B[q][i])dfs(i);
}
int main()
{
    int q,w,_;
    read(_);
    while(_--)
    {
        int S;
        read(n),read(S);
        fo(i,0,n)fo(j,0,n)B[i][j]=0;
        fo(i,1,n)z[i]=Bv[i]=0;

        fo(i,2,n)
        {
            char ch=' ';
            for(;ch<'0'||ch>'1';ch=getchar());
            fo(j,1,i-1)
            {
                if(ch=='0')B[i][j]=B[j][i]=1,++Bv[i],++Bv[j];
                ch=getchar();
            }
        }
        ans=0;
        q=0;
        fo(i,1,n)if(Bv[i]&1)++q;
        cnt=0;dfs(S);
        if(q>2||(q==2&& cnt!=2)||(q==2&& cnt==2&& Bv[S]%2==0))
        {
            printf("-1\n");
            continue;
        }
        fo(i,1,n)ans+=Bv[i];
        ans/=2;

        dfs(S);
        fo(i,1,n)if(!z[i] && Bv[i])
        {
            dfs(i);
            ans+=2;
        }
        printf("%d\n",ans);

    }
    
    return 0;
}