#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=55;
char mp[N][N];
bool vis1[N][N],vis2[N][N];
int dx4[]={0,1,0,-1};
int dy4[]={-1,0,1,0};
int dx8[]={1,1,1,0,0,-1,-1,-1};
int dy8[]={0,1,-1,1,-1,0,1,-1};
int n,m,ans,idx;
void dfs(int x,int y)
{
	vis1[x][y]=idx;
	for(int i=0;i<4;i++)
	{
		int nx=dx4[i]+x;
		int ny=dy4[i]+y;
		if(nx<=0||nx>n||ny<=0||ny>m)continue;
		if(vis1[nx][ny]||mp[nx][ny]=='0')continue;
		dfs(nx,ny);
	}
}
bool query(int x,int y)
{
	if(x<=0||y<=0||x>n||y>m)return 1;
	vis2[x][y]=1;
	for(int i=0;i<8;i++)
	{
		int nx=dx8[i]+x;
		int ny=dy8[i]+y;
		if(mp[nx][ny]=='1'&&vis1[nx][ny]!=idx)continue;
		if(vis2[nx][ny])continue;
		if(query(nx,ny))return 1;
	}
	return 0;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cin>>mp[i][j];
				vis1[i][j]=0;
			} 
		}
		ans=idx=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(vis1[i][j]||mp[i][j]=='0')continue;
				idx++;
				dfs(i,j);
				memset(vis2,0,sizeof(vis2));
				if(query(i,j))ans++;
			}
		} 
		cout<<ans<<'\n'; 
	} 
	return 0;
}

int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
		sort(b+1,b+1+n);
		idx=unique(b+1,b+1+n)-b-1;
		for(int i=1;i<=n;i++)
		{
			int t=lower_bound(b+1,b+idx+1,a[i])-b;
			a[i]=t;
		}
		int l=-1,r=n*(n-1)/2;
		while(l+1<r)
		{
			int mid=(l+r)/2;
			if(check(mid))r=mid;
			else l=mid;
		}
		cout<<r<<"\n";
	}

bool check(int x)
{
	int cnt=1,sum=0;
	int l=1;
	for(int i=1;i<=n;i++)
	{
		int num=get_sum(idx)-get_sum(a[i]);
		if(sum+num<=x)sum+=num;
		else
		{
			cnt++;
			sum=0;
			for(int j=l;j<=i-1;j++)modify(a[j],-1);
			l=i;
		}
		modify(a[i],1);
	}
	for(int j=l;j<=n;j++)modify(a[j],-1);
	return cnt<=k;
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,k,c[N],a[N],b[N],idx;
map<int,int> mp;
int lowbit(int x)
{
	return x&-x;
}
int get_sum(int x)
{
	int res=0;
	while(x)
	{
		res+=c[x];
		x-=lowbit(x);
	}
	return res;
}
void modify(int x,int val)
{
	while(x<=n)
	{
		c[x]+=val;
		x+=lowbit(x);
	}
	return ;
}
bool check(int x)
{
	int cnt=1,sum=0;
	int l=1;
	for(int i=1;i<=n;i++)
	{
		int num=get_sum(idx)-get_sum(a[i]);
		if(sum+num<=x)sum+=num;
		else
		{
			cnt++;
			sum=0;
			for(int j=l;j<=i-1;j++)modify(a[j],-1);
			l=i;
		}
		modify(a[i],1);
	}
	for(int j=l;j<=n;j++)modify(a[j],-1);
	return cnt<=k;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
		sort(b+1,b+1+n);
		idx=unique(b+1,b+1+n)-b-1;
		for(int i=1;i<=n;i++)
		{
			int t=lower_bound(b+1,b+idx+1,a[i])-b;
			a[i]=t;
		}
		int l=-1,r=n*(n-1)/2;
		while(l+1<r)
		{
			int mid=(l+r)/2;
			if(check(mid))r=mid;
			else l=mid;
		}
		cout<<r<<"\n";
	}
	return 0;
}