#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f
using namespace std;
int t,n,m,k;
char c[701][701];
int f[701][701][5];
signed main(){
	cin>>t;
	while(t--){
		cin>>n>>m>>k;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>c[i][j],f[i][j][0]=f[i][j][1]=0;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			int f1=min(f[i-1][j][0],k)+f[i-1][j][1];
			int f2=min(f[i][j-1][0],k)+f[i][j-1][1];
			if(f1>f2||(f1==f2&&f[i-1][j][0]<f[i][j-1][0])){
				f[i][j][0]=f[i-1][j][0];
				f[i][j][1]=f[i-1][j][1];
				if(c[i][j]=='?')f[i][j][0]++;
				if(c[i][j]=='1')f[i][j][1]++;
				f[i][j][0]=min(f[i][j][0],k);
			}
			else{
				f[i][j][0]=f[i][j-1][0];
				f[i][j][1]=f[i][j-1][1];
				if(c[i][j]=='?')f[i][j][0]++;
				if(c[i][j]=='1')f[i][j][1]++;
				f[i][j][0]=min(f[i][j][0],k);
			}
		}
		cout<<f[n][m][0]+f[n][m][1]<<"\n";
	}
	return 0;
}

$O(nm)$,