题目内容

小红是一位勤劳的农民，他拥有一块长$n$和宽$m$的土地。土地上的每个$1*1$的格子里种植着一种植物，每种植物都有一个编号，记作$A_{i,j}$。今天，有名商人来找小红，想购买他种植植物。

这名商人提出了$q$次请求(相互独立)：每次请求，他只想购买一个大小为长$h$宽$w$的矩形区域内的所有植物。而且，这个区域内的植物编号必须与商人提供的一个数字V不互质。

输入描述

1.一共有$t$组测试数据，每组测试数据第一行输入三个整数$n、m、q$，分别表示土地的长度、宽度和商人的请求数量。($1<=t<=5,1<=n,m<=200,1<=q<=10$)

2.接下来的$n$行，每行包含m个整数$A_{i,j}$，表示土地上每个格子的植物编号($1<=A_i,j<=1e9$)

3.接下来的$q$行中，每行包含3个整数$h、w、V$，表示商人希望检查的区域的大小。($1<=h<=200,1<=w<=200,1<=V<=1e9$)

输出描述

对于每位商人，输出一个整数，表示有多少块区域满足商人的购买条件。

样例1

输入

1
5 5 3
2 105 6 1 10
6 10 3 42 1
6 15 21 14 2
1 2 2 6 2
5 6 6 35 70
1 5 30
2 5 6
3 2 10

输出

2
0
2

说明

第一个请求需要长为$1$，宽为$5$的田中所有植物编号不与$30$互质，仅有矩形$[(3,1),(3,5)],[(5,1),(5,5)]$符合要求，因此输出$2$.

第二个请求需要长为$2$，宽为$5$的田中所有植物编号不与$6$互质，均不满足，因此输出$0$。

第二个请求需要长为$3$，宽为$2$的田中所有植物编号不与$10$互质，仅有矩形$[(1,1),(3,2)]，[(3,4),(5,5)]$符合要求，因此输出$2$