题目描述

战场局势可以用一个 $n \times m$ 的 $01$ 矩阵表示，$a_{i,j}=0$ 代表 $(i,j)$ 这个位置被敌军占领，$a_{i,j}=1$ 代表 $(i,j)$ 这个位置被我军占领。

你可以指挥飞机进行轰炸，轰炸有范围参数 $p,q$，其中 $1 \le p \le n,1 \le q \le m$，一次轰炸形如：选择 $1 \le x \le n - p + 1,1 \le y \le m - q + 1$，摧毁以 $(x,y)$ 为左上角，$(x+p-1,y+q-1)$ 为右下角的矩形区域中的所有单位。

你可以进行任意多次轰炸，一个位置的单位不会被多次摧毁，你希望在所有我军单位均未被摧毁的情况下，摧毁至少 $k$ 个敌军单位。

请计算有多少种范围参数二元组 $(p,q)$ 使得该目标可以被达成。

输入格式

本题有多组数据。第一行一个正整数 $T$（$1\le T\le 1500$），表示测试数据组数。

对于每组数据，第一行三个整数 $n,m,k$ （$1 \le n,m \le 3000,0 \le k \le nm$）。

接下来 $n$ 行，每行一个长度为 $m$ 的 $01$ 字符串描述矩阵 $a$ 的第 $i$ 行。

保证 $\sum nm \le 2.2 \times 10^7$。

输出格式

对于每组数据，输出一行一个整数表示可以达成目标的参数二元组数量。

3
5 4 4
1100
1011
0111
1001
1000
3 5 1
00010
11111
11000
5 2 4
10
01
01
10
10

4
3
2