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

const int N = 1e4 + 10;
char g[N][N];
int cnt[N][N], sum[N][N];
int dx[] = {0, 1}, dy[] = {1, 0};
int n, m, p;

void clear()
{
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)
			cnt[i][j] = sum[i][j] = 0;
}
void bfs()
{
	for(int x = 1; x <= n; x ++)
		for(int y = 1; y <= m; y ++)
		{
			if(g[x][y] == '1') sum[x][y] ++;
			else if(g[x][y] == '?' && cnt[x][y] < p)
				sum[x][y] ++, cnt[x][y] ++;
			for(int i = 0; i < 2; i ++)
			{
				int a = x + dx[i], b = y + dy[i];
				if(a > n || b > m) continue;
				if(sum[a][b] < sum[x][y] && cnt[x][y] <= p)
					sum[a][b] = sum[x][y], cnt[a][b] = cnt[x][y];
				else if(sum[a][b] == sum[x][y] && cnt[a][b] > cnt[x][y])
					cnt[a][b] = cnt[x][y];
			}
		}
}
int main()
{
	int t;
	cin >> t;
	while(t --)
	{
		cin >> n >> m >> p;
		clear();
		for(int i = 1; i <= n; i ++)
			for(int j = 1; j <= m; j ++)
				cin >> g[i][j];
		bfs();
		cout << sum[n][m] << endl;
	}
	
    return 0;
}

GESP的时候20分，现在只有50分了。

别问我为什么叫bfs，随便取的