#include <bits/stdc++.h>
using namespace std;

int n, src;
int mp[1010][1010];
int cnt[1010];
bool vis[1010];

void dfs(int x, int &sz)
{
    vis[x] = true;
    sz++;
    for (int i = 1; i <= n; i++)
        if (vis[i] == false && mp[x][i] == 1)
            dfs(i, sz);
}

void work()
{
    scanf("%d%d", &n, &src);
    for (int i = 1; i <= n; i++) cnt[i] = vis[i] = 0;
    int sum = 0;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
        mp[i][j] = 0;
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            int x; scanf("%1d", &x);
            if (x == 0)
            {
                cnt[i]++;
                cnt[j]++;
                sum++;
                mp[i][j] = 1;
                mp[j][i] = 1;
            }
        }
    }
    
    int tot = 0;
    for (int i = 1; i <= n; i++)
    {
        if (cnt[i] % 2 != 0) tot++; 
    }
    if (tot > 2 || (tot == 2 && cnt[src] % 2 == 0))
    {
        puts("-1");
    }
    else
    {
        int block = 0;
        for (int i = 1; i <= n; i++)
        {
            if (vis[i] == 0)
            {
                int size = 0;
                dfs(i, size);
                if (i == src || size > 1) block++;
            }
        }
        printf("%d\n", (block - 1) * 2 + sum);
    }
}


int main()
{
    int t; scanf("%d", &t);
    while (t--) work();
    return 0;
}