数字矩阵

题号：NC206587
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小L老师在黑板上写下一个n行m列只含有数字的矩阵。写完后，小L老师就询问一个问题，

在这个数字矩阵中有多少个包含1的子矩阵。聪明的小明很快就能想出来并给出了答案。于是，

小L老师就对这个子矩阵加了一些限制条件：

1.子矩阵有4个整数x1,y1,x2,y2来定义，(1≤x1<x2≤n,1≤y1<y2≤m)

2.子矩阵的4个顶角中数字要相同。

3.子矩阵最多包含k个1.

小L老师这次的问题是在这矩阵中满足上面所诉条件的子矩阵的个数。小明一下子得不出答案，聪明的你

能帮助小明解决这个问题嘛

第一行一个整数T（1≤T≤100），表示共有T组测试数据。
对于每组测试数据，第一行三个整数n,m,k(2≤n,m≤100,0≤k≤n*m),表示数字矩阵的行数和列数,还有最多包含1的个数。
接下来有n行只含有数字的字符串，每行m个字符

输出满足子矩阵限制条件的个数。

示例1

复制

复制

2
1