Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef found a matrix $A$ with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$), where for each row $r$ and column $c$, the cell in row $r$ and column $c$ (denoted by $(r,c)$) contains an integer $A_{r,c}$.

This matrix has two interesting properties:
The integers in each row form a non-decreasing sequence, i.e. for each valid $i$, $A_{i,1} ≤ A_{i,2} ≤ \ldots ≤ A_{i,M}$.
The integers in each column also form a non-decreasing sequence, i.e. for each valid $j$, $A_{1,j} ≤ A_{2,j} ≤ \ldots ≤ A_{N,j}$.

A $K$-worthy [submatrix] is a square submatrix of $A$, i.e. a submatrix with $l$ rows and $l$ columns, for any integer $l$, such that the average of all the integers in this submatrix is $≥ K$.

Chef wants you to find the number of $K$-worthy submatrices of $A$.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains three space-separated integers $N$, $M$ and $K$.
$N$ lines follow. For each valid $i$, the $i$-th of these lines contains $M$ space-separated integers $A_{i,1}, A_{i,2}, A_{i,3}, \ldots, A_{i,M}$.

------ Output ------
For each test case, print a single line containing one integer ― the number of $K$-worthy submatrices of $A$.

------ Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N \cdot M ≤ 10^{6}$
$N ≤ M$
$0 ≤ K ≤ 10^{9}$
$0 ≤ A_{r,c} ≤ 10^{9}$ for each valid $r,c$
the sum of $N \cdot M$ over all test cases does not exceed $10^{6}$

------ Subtasks ------
Subtask #1 (15 points): the sum of $N \cdot M$ over all test cases does not exceed $10^{3}$

Subtask #2 (25 points): the sum of $N \cdot M$ over all test cases does not exceed $4 \cdot 10^{5}$

Subtask #3 (60 points): original constraints

----- Sample Input 1 ------
1

3 3 4

2 2 3

3 4 5

4 5 5
----- Sample Output 1 ------
7
----- explanation 1 ------
Example case 1: The following are the seven $4$-worthy submatrices:
- $
$\begin{bmatrix}$
3 & 4 \
4 & 5 \
\end{bmatrix}with average $4$; this matrix occurs only once
- $
$\begin{bmatrix}$
4 & 5 \
5 & 5 \
\end{bmatrix}with average $4.75$; this matrix also occurs only once
- $
$\begin{bmatrix}$
4 \
\end{bmatrix}with average $4$; we find this matrix twice in $A$
- $
$\begin{bmatrix}$
5 \
\end{bmatrix}with average $5$; we find this matrix $3$ times in $A$

见题面

见题面