题面描述

⼩杨有⼀个有⼀个 n x m 的矩阵，仅包含0 1 ? 三种字符。矩阵的⾏从上到下编号依次为1,2,…,n，列从左到右编号依次为1,2,…,m编号。⼩杨开始在矩阵的左上角（1,1），⼩杨只能向下或者向右移动，最终到达右下角（n, m）时停⽌，在移动的过程中每经过⼀个字符1得分会增加⼀分（包括起点和终点），经过其它字符则分数不变。⼩杨的初始分数为0分。 ⼩杨可以将矩阵中不超过x个字符 ? 变为字符 1。⼩杨在修改矩阵后，会以最优的策略从左上角移动到右下角。他想知道⾃⼰最多能获得多少分。

输入格式

第⼀⾏包含⼀个正整数 t ，代表测试⽤例组数。 接下来是 t 组测试⽤例 。对于每组测试⽤例 ，⼀共 n + 1 ⾏。 第⼀⾏包含三个正整数 n, m, x ，含义如题⾯所⽰。 之后 n ⾏ ，每⾏包含⼀个长度为 m 且仅包含 01? 三种字符的字符串。

输出格式

对于每组测试⽤例 ，输出⼀⾏⼀个整数 ，代表最优策略下⼩杨的得分最多是多少。

样例输出

2
3 3 1 000
111
01?   3 3 1 000
?0? 01?

4
2

样例说明

对于全部数据 ，保证有 1 ≤ t ≤ 10 ，1 ≤ n, m ≤ 500, 1 ≤ z ≤ 300 ，同时保证所有测试⽤例 n x m 的总和不超过 2 . 5 x 105。