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$

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Amortized analysis


Solutions:
def worthy():
	testcases = int(input())
	while testcases:
		(m, n, k) = map(int, input().strip().split(' '))
		matrix = [[0 for x in range(n)] for y in range(m)]
		matrix = []
		for i in range(m):
			r = list(map(int, input().strip().split(' ')))
			matrix.append(r)
		auxillary = [[0 for x in range(n + 1)] for y in range(m + 1)]
		for i in range(m + 1):
			auxillary[i][0] = 0
		for j in range(n + 1):
			auxillary[0][j] = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				auxillary[i][j] = matrix[i - 1][j - 1]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				auxillary[i][j] += auxillary[i][j - 1]
		for j in range(1, n + 1):
			for i in range(1, m + 1):
				auxillary[i][j] += auxillary[i - 1][j]
		result = 0
		for p in range(1, m + 1):
			for i in range(1, m - p + 2):
				l = 1
				h = n - p + 1
				mid = 0
				q = 0
				flag = 0
				while l <= h:
					mid = int((l + h) / 2)
					out = auxillary[i + p - 1][mid + p - 1] - auxillary[i + p - 1][mid - 1] - auxillary[i - 1][mid + p - 1] + auxillary[i - 1][mid - 1]
					if out >= k * p * p:
						h = mid - 1
						q = mid
						flag = 1
					else:
						l = mid + 1
				if flag == 1:
					result += n - p - q + 2
		print(result)
		testcases -= 1
worthy()


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	A = [[int(c) for c in input().split()] for r in range(n)]
	grid = [[0 for c in range(m + 1)] for r in range(n + 1)]
	for r in range(1, n + 1):
		for c in range(1, m + 1):
			grid[r][c] = A[r - 1][c - 1] + grid[r - 1][c] + grid[r][c - 1] - grid[r - 1][c - 1]
	ans = 0
	for sz in range(1, n + 1):
		for r in range(sz, n + 1):
			low = sz
			high = m
			while low <= high:
				mid = (low + high) // 2
				yellow = grid[r][mid] - grid[r - sz][mid] - grid[r][mid - sz] + grid[r - sz][mid - sz]
				if yellow // (sz * sz) >= k:
					high = mid - 1
					mid1 = mid
				else:
					low = mid + 1
			if low <= m:
				ans += m - mid1 + 1
	print(ans)


def testcase():
	(n, m, k) = map(int, input().split())
	A = [[int(c) for c in input().split()] for r in range(n)]
	grid = [[0 for c in range(m + 1)] for r in range(n + 1)]
	for r in range(1, n + 1):
		for c in range(1, m + 1):
			grid[r][c] = A[r - 1][c - 1] + grid[r - 1][c] + grid[r][c - 1] - grid[r - 1][c - 1]
	phani = 0
	for sz in range(1, n + 1):
		for r in range(sz, n + 1):
			low = sz
			high = m
			while low <= high:
				mid = (low + high) // 2
				yellow = grid[r][mid] - grid[r - sz][mid] - grid[r][mid - sz] + grid[r - sz][mid - sz]
				if yellow // (sz * sz) >= k:
					high = mid - 1
					mid1 = mid
				else:
					low = mid + 1
			if low <= m:
				phani += m - mid1 + 1
	print(phani)
for t in range(int(input())):
	testcase()


def test_case():
	(n, m, k) = map(int, input().strip().split())
	A = [[int(x) for x in input().strip().split()] for y in range(n)]
	G = [[0 for x in range(m + 1)] for y in range(n + 1)]
	for row in range(1, n + 1):
		for col in range(1, m + 1):
			G[row][col] = A[row - 1][col - 1] + G[row - 1][col] + G[row][col - 1] - G[row - 1][col - 1]
	size = min(n, m)
	ps = 0
	for sz in range(1, size + 1):
		for row in range(sz, n + 1):
			low = sz
			high = m
			while low <= high:
				mid = (low + high) // 2
				ssum = G[row][mid] - G[row - sz][mid] - G[row][mid - sz] + G[row - sz][mid - sz]
				if ssum // (sz * sz) >= k:
					high = mid - 1
					curr = mid
				else:
					low = mid + 1
			if low <= m:
				ps += m - curr + 1
	print(ps)
for _ in range(int(input().strip())):
	test_case()


import sys

def binary_search(arr, col, low, high, order, min_value):
	while low < high:
		mid = (low + high) // 2
		if (arr[mid][col] - arr[mid - order][col] - arr[mid][col - order] + arr[mid - order][col - order]) / (order * order) >= min_value:
			high = mid - 1
		else:
			low = mid + 1
	return low

def binary_search2(arr, row, low, high, order, min_value):
	while low < high:
		mid = (low + high) // 2
		if (arr[row][mid] - arr[row - order][mid] - arr[row][mid - order] + arr[row - order][mid - order]) / (order * order) >= min_value:
			high = mid - 1
		else:
			low = mid + 1
	return low

def count(m, n, k, arr):
	matrix_count = 0
	for i in range(1, m + 1):
		row_sum = 0
		for j in range(1, n + 1):
			arr[i][j] = row_sum + arr[i][j]
			row_sum = arr[i][j]
	for i in range(1, n + 1):
		col_sum = 0
		for j in range(1, m + 1):
			arr[j][i] = col_sum + arr[j][i]
			col_sum = arr[j][i]
	for order in range(1, m + 1):
		for i in range(binary_search(arr, n, order, m, order, k), m + 1):
			for j in range(binary_search2(arr, i, order, n, order, k), n + 1):
				if (arr[i][j] - arr[i - order][j] - arr[i][j - order] + arr[i - order][j - order]) / (order * order) >= k:
					matrix_count += n - j + 1
					break
	return matrix_count
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	arr = [[0] * (m + 1)]
	for row in range(n):
		temp = list(map(int, sys.stdin.readline().split()))
		temp.insert(0, 0)
		arr.append(temp)
	print(str(count(n, m, k, arr)))


def solve(A, R, C, K):
	RLE = [[0] * (C + 1) for _ in range(R + 1)]
	for r in range(R):
		for c in range(C):
			RLE[r + 1][c + 1] = A[r][c]
	for r in range(1, R + 1):
		for c in range(1, C + 1):
			RLE[r][c] += RLE[r][c - 1]
	for r in range(1, R + 1):
		for c in range(1, C + 1):
			RLE[r][c] += RLE[r - 1][c]
	res = 0
	for sz in range(1, R + 1):
		for r in range(1, R - sz + 2):
			j = flag = 0
			(lo, hi) = (1, C - sz + 1)
			while lo <= hi:
				mi = lo + hi >> 1
				cand = RLE[r + sz - 1][mi + sz - 1] - RLE[r - 1][mi + sz - 1] - RLE[r + sz - 1][mi - 1] + RLE[r - 1][mi - 1]
				if cand >= K * sz * sz:
					j = mi
					flag = 1
					hi = mi - 1
				else:
					lo = mi + 1
			if flag == 1:
				res += C - sz - j + 2
	return res
T = int(input())
for t in range(T):
	(R, C, K) = map(int, input().split())
	A = []
	for r in range(R):
		row = list(map(int, input().split()))
		A.append(row)
	res = solve(A, R, C, K)
	print(res)


for iiiii in range(int(input())):
	(n, m, k) = map(int, input().split())
	dp = []
	for i in range(n):
		r = []
		for j in range(m):
			r.append(0)
		dp.append(r)
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	dp[0][0] = l[0][0]
	for j in range(1, m):
		dp[0][j] = l[0][j] + dp[0][j - 1]
	for i in range(1, n):
		dp[i][0] = l[i][0] + dp[i - 1][0]
	for i in range(1, n):
		for j in range(1, m):
			dp[i][j] = l[i][j] - dp[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1]
	ad = 0
	sub = min(n, m)
	itr = 0
	for i in range(n):
		maxc = 1
		for j in range(m):
			for t in range(max(maxc, 1), sub + 1):
				if t - 1 <= i and t - 1 <= j:
					s = 0
					if i == t - 1 or j == t - 1:
						if i == t - 1 and j == t - 1:
							s = dp[i][j]
						elif i == t - 1:
							s = dp[i][j] - dp[i][j - t]
						else:
							s = dp[i][j] - dp[i - t][j]
					else:
						s = dp[i][j] - dp[i - t][j] - dp[i][j - t] + dp[i - t][j - t]
					if s >= t * t * k:
						ad += m - j
						maxc = t + 1
					else:
						break
				itr += 1
	print(ad)


def getVal(dp, k, i, j):
	if i < 0 or j < 0:
		print('ERROR')
		exit()
	return dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k]

def getIndex(li, i, start, end, sz, k):
	pos = -1
	while start <= end:
		mid = start + (end - start) // 2
		val = getVal(dp, sz, i, mid) / (sz * sz)
		if val < k:
			start = mid + 1
		else:
			pos = mid
			end = mid - 1
	return pos

def solve(dp, n, m, k):
	total = 0
	for sz in range(1, n + 1):
		for i in range(sz, n + 1):
			val = getVal(dp, sz, i, m) / (sz * sz)
			if val >= k:
				ind = getIndex(dp[i], i, sz, m, sz, k)
				total += m - ind + 1
	return total
for t in range(int(input())):
	(n, m, k) = map(int, input().split())
	dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
	for i in range(1, n + 1):
		for (j, val) in enumerate(input().split(), start=1):
			dp[i][j] = dp[i][j - 1] + int(val)
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			dp[i][j] += dp[i - 1][j]
	print(solve(dp, n, m, k))


def count(mat, n, m, k, order):
	c = 0
	mn = min(n, m)
	order = 1
	d = 0
	while order < mn + 1:
		i = order
		j = m
		while i < n + 1:
			sum = mat[i][j] - mat[i - order][j] - mat[i][j - order] + mat[i - order][j - order]
			if sum < k * order * order:
				i = i + 1
			else:
				start = order
				end = m
				while start <= end:
					mid = (start + end) // 2
					x = i - order + 1
					y = mid - order + 1
					sum = mat[i][mid] - mat[x - 1][mid] - mat[i][y - 1] + mat[x - 1][y - 1]
					if sum >= k * order * order:
						end = mid - 1
						ans = mid
					else:
						start = mid + 1
				c += m - ans + 1
				i = i + 1
		order = order + 1
	return c
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	l = [list(map(int, input().split())) for i in range(n)]
	l1 = []
	l2 = []
	for i in range(n):
		sum = 0
		for j in range(m):
			sum += l[i][j]
			l[i][j] = sum
	for i in range(m):
		sum = 0
		for j in range(n):
			sum += l[j][i]
			l[j][i] = sum
	l.insert(0, [0] * m)
	for i in range(n + 1):
		l[i].insert(0, 0)
	print(count(l, n, m, k, 1))


for z in range(int(input())):
	(n, m, k) = map(int, input().split())
	matrix = []
	for y in range(n):
		temp = list(map(int, input().split()))
		temp.insert(0, 0)
		matrix.append(temp)
	temp = []
	for i in range(m + 1):
		temp.append(0)
	matrix.insert(0, temp)
	for i in range(n + 1):
		Sum = 0
		for j in range(m + 1):
			Sum += matrix[i][j]
			matrix[i][j] = Sum
	for i in range(m + 1):
		Sum = 0
		for j in range(n + 1):
			Sum += matrix[j][i]
			matrix[j][i] = Sum
	order = 1
	count = 0
	while order < n + 1:
		i = order
		j = m
		while i < n + 1:
			x = i - order + 1
			y = j - order + 1
			z = matrix[i][j] - matrix[x - 1][j] - matrix[i][y - 1] + matrix[x - 1][y - 1]
			if z / (order * order) < k:
				i += 1
			else:
				start = order
				end = m
				while start <= end:
					mid = (start + end) // 2
					x = i - order + 1
					y = mid - order + 1
					z = matrix[i][mid] - matrix[x - 1][mid] - matrix[i][y - 1] + matrix[x - 1][y - 1]
					if z / (order * order) < k:
						start = mid + 1
					else:
						ans = mid
						end = mid - 1
				count += m - ans + 1
				i += 1
		order += 1
	print(count)


import numpy as np
for i in range(int(input())):
	(n, m, k) = [int(ii) for ii in input().split()]
	ll = []
	for ii in range(n):
		ll.append([int(iii) for iii in input().split()])
	ll = np.array(ll)
	for r in range(len(ll) - 1):
		ll[r + 1] += ll[r]
	for r in range(len(ll[0]) - 1):
		ll[:, r + 1] += ll[:, r]
	ll = [(ll[0] * 0).tolist()] + ll.tolist()
	ll = np.array(ll).T
	ll = [(ll[0] * 0).tolist()] + ll.tolist()
	ll = np.array(ll).T
	r = 0
	c = 0
	ans = 0
	l = min(n, m)
	while r < n:
		l = min(n - r, m)
		while c < m and l > 0:
			if l > m - c:
				l -= 1
			avg = (ll[r + l, c + l] - ll[r + l, c] - ll[r, c + l] + ll[r, c]) / l / l
			if avg >= k:
				ans += m - c - l + 1
				l -= 1
			else:
				c += 1
		r += 1
		c = 0
	print(ans)


def solve(sum, n, m, key):
	c = 0
	for k in range(1, n + 1):
		for i in range(k - 1, n):
			(low, high, j, total) = (k - 1, m - 1, 0, 0)
			while low <= high:
				j = (low + high) // 2
				total = sum[i][j]
				if i - k >= 0:
					total = total - sum[i - k][j]
				if j - k >= 0:
					total = total - sum[i][j - k]
				if i - k >= 0 and j - k >= 0:
					total = total + sum[i - k][j - k]
				if total / (k * k) >= key:
					high = j - 1
				else:
					low = j + 1
			if total / (k * k) >= key:
				c += m - j
			else:
				c += m - j - 1
	return c
for _ in range(int(input())):
	(n, m, key) = map(int, input().split())
	matrix = [list(map(int, input().split())) for j in range(n)]
	t = [[0 for i in range(m)] for j in range(n)]
	t[0][0] = matrix[0][0]
	for i in range(m):
		t[0][i] = t[0][i - 1] + matrix[0][i]
	for i in range(n):
		t[i][0] = t[i - 1][0] + matrix[i][0]
	for i in range(1, n):
		for j in range(1, m):
			t[i][j] = t[i - 1][j] + t[i][j - 1] + matrix[i][j] - t[i - 1][j - 1]
	print(solve(t, n, m, key))


def pp():
	llll = list(range(1, 7))

def summon(mat, n, m, k, o):
	c = 0
	p = 0
	x = min(n, m)
	while o < x + 1:
		i = o
		j = m
		while i < n + 1:
			a = i - o + 1
			b = j - o + 1
			z = mat[i][j] - mat[a - 1][j] - mat[i][b - 1] + mat[a - 1][b - 1]
			if z // (o * o) < k:
				i += 1
			else:
				s = o
				e = m
				while s <= e:
					mi = (s + e) // 2
					a = i - o + 1
					b = mi - o + 1
					z = mat[i][mi] - mat[a - 1][mi] - mat[i][b - 1] + mat[a - 1][b - 1]
					if z // (o * o) < k:
						s = mi + 1
					else:
						p = mi
						e = mi - 1
				c += m - p + 1
				i += 1
		o += 1
	return c
t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	ls = []
	for i in range(n):
		pp()
		ls += [list(map(int, input().split()))]
	ls1 = [[0 for x in range(m + 1)] for y in range(n + 1)]
	for i in range(n):
		for j in range(m):
			ls1[i + 1][j + 1] = ls[i][j]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			pp()
			ls1[i][j] += ls1[i - 1][j] + ls1[i][j - 1] - ls1[i - 1][j - 1]
	ans = summon(ls1, n, m, k, 1)
	print(ans)


def MyFunc(matrix, n1, n2, k, our_con):
	con1 = 0
	con2 = 0
	x = min(n1, n2)
	while our_con < x + 1:
		rows = our_con
		col = n2
		while rows < n1 + 1:
			a = rows - our_con + 1
			b = col - our_con + 1
			z = matrix[rows][col] - matrix[a - 1][col] - matrix[rows][b - 1] + matrix[a - 1][b - 1]
			if z // (our_con * our_con) < k:
				rows += 1
			else:
				con3 = our_con
				e = n2
				while con3 <= e:
					mi = (con3 + e) // 2
					a = rows - our_con + 1
					b = mi - our_con + 1
					z = matrix[rows][mi] - matrix[a - 1][mi] - matrix[rows][b - 1] + matrix[a - 1][b - 1]
					if z // (our_con * our_con) < k:
						con3 = mi + 1
					else:
						con2 = mi
						e = mi - 1
				con1 += n2 - con2 + 1
				rows += 1
		our_con += 1
	return con1
test = int(input())
for rows in range(test):
	(n1, n2, k) = map(int, input().split())
	ls = []
	for rows in range(n1):
		ls += [list(map(int, input().split()))]
	ls1 = [[0 for x in range(n2 + 1)] for y in range(n1 + 1)]
	for rows in range(n1):
		for col in range(n2):
			ls1[rows + 1][col + 1] = ls[rows][col]
	for rows in range(1, n1 + 1):
		for col in range(1, n2 + 1):
			ls1[rows][col] += ls1[rows - 1][col] + ls1[rows][col - 1] - ls1[rows - 1][col - 1]
	res = MyFunc(ls1, n1, n2, k, 1)
	print(res)


from math import *
from collections import *

def pref_mat(n, m, l):
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			l[i][j] += l[i][j - 1]
	for i in range(1, m + 1):
		for j in range(1, n + 1):
			l[j][i] += l[j - 1][i]
	return l

def bins_panda(n, m, k, l):
	cnt = 0
	for i in range(1, n + 1):
		for j in range(1, n - i + 2):
			(low, up) = (1, m - i + 1)
			fl = False
			x = 0
			x1 = 0
			while low <= up:
				x = (low + up) // 2
				s = l[i + j - 1][x + i - 1] - l[i + j - 1][x - 1] - l[j - 1][x + i - 1] + l[j - 1][x - 1]
				if s >= k * i ** 2:
					up = x - 1
					fl = True
					x1 = x
				else:
					low = x + 1
			if fl:
				cnt += m - i - x1 + 2
	return cnt
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	l = [[0 for x3 in range(m + 1)]]
	for xx in range(n):
		l.append([0] + list(map(int, input().split())))
	l1 = pref_mat(n, m, l)
	print(bins_panda(n, m, k, l1))


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	matrix = []
	for _ in range(n):
		matrix.append(list(map(int, input().split())))
	for i in range(n):
		for j in range(1, m):
			matrix[i][j] += matrix[i][j - 1]
	for i in range(m):
		for j in range(1, n):
			matrix[j][i] += matrix[j - 1][i]
	for i in range(n):
		matrix[i].insert(0, 0)
	matrix.insert(0, [0 for _ in range(len(matrix[0]))])
	count = 0
	order = 1
	while order < n + 1:
		i = order
		j = m
		for i in range(order, n + 1):
			a = i - order + 1
			b = j - order + 1
			z = matrix[i][j] - matrix[a - 1][j] - matrix[i][b - 1] + matrix[a - 1][b - 1]
			if z / (order * order) < k:
				i += 1
			else:
				start = order
				end = m
				while start <= end:
					mid = (start + end) // 2
					a = i - order + 1
					b = mid - order + 1
					z = matrix[i][mid] - matrix[a - 1][mid] - matrix[i][b - 1] + matrix[a - 1][b - 1]
					if z / (order * order) < k:
						start = mid + 1
					else:
						res = mid
						end = mid - 1
				count += m - res + 1
		order += 1
	print(count)


testcase = int(input())
for _ in range(testcase):
	(n, m, k) = map(int, input().split())
	array = []
	total_sum = []
	answer = 0
	for x in range(n):
		array.append([int(y) for y in input().split()])
	total_sum.append([])
	for i in range(n + 1):
		for j in range(m + 1):
			if i == 0:
				total_sum[i].append(0)
			elif j == 0:
				total_sum.append([0])
			else:
				total_sum[i].append(array[i - 1][j - 1])
	for i in range(n + 1):
		previous_value = 0
		for j in range(m + 1):
			total_sum[i][j] += previous_value
			previous_value = total_sum[i][j]
	for j in range(m + 1):
		previous_value = 0
		for i in range(n + 1):
			total_sum[i][j] += previous_value
			previous_value = total_sum[i][j]
	minimum_value = min(n, m)
	for order in range(1, minimum_value + 1):
		start = order
		end = m
		while start >= 1 and start <= n and (end >= 1) and (end <= m):
			if (total_sum[start][end] - total_sum[start - order][end] - total_sum[start][end - order] + total_sum[start - order][end - order]) / (order * order) >= k:
				answer += n - start + 1
				end -= 1
			else:
				start += 1
	print(answer)


def counting(dp, n, m, k, ord):
	i = ord
	j = m
	count = 0
	for i in range(ord, n + 1):
		x = i - ord + 1
		y = j - ord + 1
		sumSubMat = dp[i][j] - dp[x - 1][j] - dp[i][y - 1] + dp[x - 1][y - 1]
		if sumSubMat / ord ** 2 >= k:
			low = ord
			high = m
			while low <= high:
				mid = (low + high) // 2
				x = i - (ord - 1)
				y = mid - (ord - 1)
				sumsub = dp[i][mid] - dp[x - 1][mid] - dp[i][y - 1] + dp[x - 1][y - 1]
				if sumsub / ord ** 2 < k:
					low = mid + 1
				else:
					ind = mid
					high = mid - 1
			count += m - ind + 1
	return count

def subb(matrix, n, m, k):
	dp = [[0 for _ in range(m + 1)] for __ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			dp[i + 1][j + 1] = matrix[i][j]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
	mini = min(n, m)
	count = 0
	for i in range(1, mini + 1):
		count += counting(dp, n, m, k, i)
	return count
for t in range(int(input())):
	(n, m, k) = map(float, input().split())
	n = int(n)
	m = int(m)
	matrix = []
	for i in range(n):
		x = list(map(float, input().split()))
		matrix.append(x)
	print(subb(matrix, n, m, k))


def func(y, z, Am, size):
	return Am[y][z] - Am[y - size][z] - Am[y][z - size] + Am[y - size][z - size]
T = int(input())
for _ in range(T):
	(N, M, K) = map(int, input().split())
	A = list()
	count = 0
	for i in range(N):
		A.append(list(map(lambda x: int(x) - K, input().split())))
	Am = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
	for i in range(1, N + 1):
		for j in range(1, M + 1):
			Am[i][j] = Am[i][j - 1] + A[i - 1][j - 1]
			if A[i - 1][j - 1] >= 0:
				count += 1
	for j in range(1, M + 1):
		for i in range(1, N + 1):
			Am[i][j] = Am[i - 1][j] + Am[i][j]
	for size in range(2, N + 1):
		for i in range(size, N + 1):
			if func(i, size, Am, size) >= 0:
				count += M - size + 1
			elif func(i, M, Am, size) < 0:
				continue
			else:
				low = size
				high = M
				mid = 0
				while low < high - 1:
					mid = (high - low) // 2 + low
					if func(i, mid, Am, size) < 0:
						low = mid
					else:
						high = mid
				count += M - high + 1
	print(count)


from bisect import bisect_left as bis
from collections import defaultdict
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = []
	last = []
	for i in range(n):
		li = list(map(int, input().split()))
		a.append(li)
		last.append(li[-1])
	if n == 1:
		if a[0][-1] >= k:
			print(m - bis(a[0], k))
			continue
		else:
			print(0)
			continue
	if m == 1:
		if a[-1][0] >= k:
			print(n - bis(last, k))
			continue
		else:
			print(0)
			continue
	if a[0][0] >= k:
		ans = 0
		for i in range(min(n, m)):
			ans += (n - i) * (m - i)
		print(ans)
		continue
	if a[-1][-1] < k:
		print(0)
		continue
	row1 = bis(last, k)
	ans = 0
	low = defaultdict(lambda : 0)
	bise = defaultdict(lambda : 0)
	b = [[0] * (m + 1) for i in range(n + 1)]
	for i in range(n):
		for j in range(m):
			b[i + 1][j + 1] = a[i][j]
			b[i + 1][j + 1] += b[i + 1][j]
	for i in range(2, n + 1):
		for j in range(1, m + 1):
			b[i][j] += b[i - 1][j]
	for i in range(row1, n):
		bise[i] = bis(a[i], k)
		ans += m - bise[i]
		if bise[i] == 0:
			ans += (n - 1 - i) * m
			break
	for size in range(2, min(n, m) + 1):
		col = 10
		for i in range(max(0, row1 - size + 1), n - size + 1):
			col1 = bise[i + size - 1]
			st = max(0, col1 - size + 1, low[i + size - 1] - size + 2)
			for j in range(st, m - size + 1):
				if b[i + size][j + size] - b[i + size][j] - b[i][j + size] + b[i][j] >= k * size * size:
					ans += m - j - size + 1
					col = j
					break
				low[i + size - 1] = j + size - 1
				if j + size - 1 == m - 1:
					row1 += 1
			if col == 0:
				ans += (n - i - size) * (m - size + 1)
				break
	print(ans)


import sys
t = int(sys.stdin.readline())
while t:
	(n, m, k) = list(map(int, sys.stdin.readline().split()))
	A = list()
	A.append([0] * (m + 1))
	for i in range(n):
		A.append([0] + list(map(int, sys.stdin.readline().split())))
	for i in range(n + 1):
		prev = 0
		for j in range(m + 1):
			A[i][j] += prev
			prev = A[i][j]
	for i in range(m + 1):
		prev = 0
		for j in range(n + 1):
			A[j][i] += prev
			prev = A[j][i]
	ans = 0
	B = []
	for u in range(1, n + 1):
		u2 = u * u
		for i in range(1, n - u + 2):
			low = 1
			high = m - u + 1
			flag = 0
			p = 0
			while low <= high:
				mid = (high + low) // 2
				smm = A[i + u - 1][mid + u - 1] - A[i + u - 1][mid - 1] - A[i - 1][mid + u - 1] + A[i - 1][mid - 1]
				if smm >= k * u2:
					high = mid - 1
					p = mid
					flag = 1
				else:
					low = mid + 1
			if flag == 1:
				ans += m - u - p + 2
	print(ans)
	t -= 1


def countGreater(j, L, u, x, z):
	leftGreater = u + 1
	mo = u + 1
	while L <= u:
		sumi = 0
		l = int(L + (u - L) / 2)
		if j - x + 1 == 0:
			if l - x + 1 > 0:
				sumi = cot[j][l] - cot[j][l - x]
			else:
				sumi = cot[j][l]
		elif l - x + 1 > 0:
			sumi = cot[j][l] - cot[j - x][l] - (cot[j][l - x] - cot[j - x][l - x])
		else:
			sumi = cot[j][l] - cot[j - x][l]
		if sumi / (x * x) >= z:
			leftGreater = l
			u = l - 1
		else:
			L = l + 1
	return mo - leftGreater

def cou(k, v):
	count = 0
	h = 10 ** 6
	for j in range(k - 1, n):
		gh = countGreater(j, k - 1, m - 1, k, v)
		count = count + gh
		if gh == m - (k - 1):
			count = count + (n - (j + 1)) * (m - (k - 1))
			break
	return count
q = int(input())
for i in range(q):
	(n, m, r) = map(int, input().split())
	cot = []
	for j in range(n):
		cot.append(list(map(int, input().split())))
	mount = 0
	bount = 0
	for j in range(n):
		mount = 0
		for l in range(m):
			mount = mount + cot[j][l]
			if j == 0:
				cot[j][l] = mount
			else:
				cot[j][l] = mount + cot[j - 1][l]
	for j in range(1, min(n, m) + 1):
		bount = bount + cou(j, r)
	print(bount)


import sys
t = int(sys.stdin.readline())
for i in range(0, t):
	(n, m, k) = map(int, sys.stdin.readline().split())
	mat = []
	a = []
	for j in range(0, m + 1):
		a.append(0)
	mat.append(a)
	for j in range(0, n):
		arr = list(map(int, sys.stdin.readline().split()))
		arr.insert(0, 0)
		mat.append(arr)
	for j in range(0, n + 1):
		s = 0
		for p in range(0, m + 1):
			s += mat[j][p]
			mat[j][p] = s
	for j in range(0, m + 1):
		s = 0
		for p in range(0, n + 1):
			s += mat[p][j]
			mat[p][j] = s
	size = 1
	ans = 0
	lmax = min(n, m)
	while size < lmax + 1:
		p = size
		q = m
		while p < n + 1:
			x = p - size + 1
			y = q - size + 1
			z = mat[p][q] - mat[x - 1][q] - mat[p][y - 1] + mat[x - 1][y - 1]
			if z / (size * size) < k:
				p += 1
			else:
				start = size
				end = m
				while start <= end:
					mid = (start + end) // 2
					x = p - size + 1
					y = mid - size + 1
					z = mat[p][mid] - mat[x - 1][mid] - mat[p][y - 1] + mat[x - 1][y - 1]
					if z / (size * size) < k:
						start = mid + 1
					else:
						index = mid
						end = mid - 1
				ans += m - index + 1
				p += 1
		size += 1
	print(ans)


t = int(input())
while t:
	t -= 1
	(n, m, k) = map(int, input().split())
	a11 = []
	for i in range(n):
		a = list(map(int, input().split()))
		a11.append(a)
	a1 = [[0 for x in range(m)] for y in range(n)]
	a1[0][0] = a11[0][0]
	for i in range(1, m):
		a1[0][i] = a1[0][i - 1] + a11[0][i]
	for i in range(0, n):
		a1[i][0] = a1[i - 1][0] + a11[i][0]
	for i in range(1, n):
		for j in range(1, m):
			a1[i][j] = a1[i - 1][j] + a1[i][j - 1] - a1[i - 1][j - 1] + a11[i][j]
	ans = 0
	x = min(n, m)
	for i in range(n):
		max1 = 1
		for j in range(m):
			for l in range(max(max1, 1), x + 1):
				if l - 1 <= i and l - 1 <= j:
					s = 0
					if i == l - 1 or j == l - 1:
						if i == l - 1 and j == l - 1:
							s = a1[i][j]
						elif i == l - 1:
							s = a1[i][j] - a1[i][j - l]
						else:
							s = a1[i][j] - a1[i - l][j]
					else:
						s = a1[i][j] - a1[i - l][j] - a1[i][j - l] + a1[i - l][j - l]
					if s >= l * l * k:
						ans += m - j
						max1 = l + 1
					else:
						break
	print(ans)


def fun(mat, n, m, k, order):
	c = 0
	mini = min(n, m)
	while order < mini + 1:
		i = order
		j = m
		while i < n + 1:
			x = i - order + 1
			y = j - order + 1
			z = mat[i][j] - mat[x - 1][j] - mat[i][y - 1] + mat[x - 1][y - 1]
			if z / (order * order) < k:
				i += 1
			else:
				start = order
				end = m
				while start <= end:
					mid = (start + end) // 2
					x = i - order + 1
					y = mid - order + 1
					z = mat[i][mid] - mat[x - 1][mid] - mat[i][y - 1] + mat[x - 1][y - 1]
					if z / (order * order) < k:
						start = mid + 1
					else:
						ans = mid
						end = mid - 1
				c += m - ans + 1
				i += 1
		order += 1
	return c
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	mat = []
	for i in range(n):
		mat.append(list(map(int, input().split())))
	for i in range(n):
		s = 0
		for j in range(m):
			s += mat[i][j]
			mat[i][j] = s
	for i in range(m):
		s = 0
		for j in range(n):
			s += mat[j][i]
			mat[j][i] = s
	for i in range(n):
		mat[i].insert(0, 0)
	mat.insert(0, [0] * (m + 1))
	print(fun(mat, n, m, k, 1))


T = int(input())
for _ in range(1, T + 1):
	(n, m, val) = [int(j) for j in input().split()]
	aa = []
	for i in range(n):
		aa.append([int(j) for j in input().split()])
	a = [[0] * (m + 1) for _ in range(n + 1)]

	def doa():
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + aa[i - 1][j - 1]
	doa()

	def calculate():
		ans = 0
		for side in range(1, n + 1):
			for i in range(1, n - side + 2, 1):
				l = 1
				r = m - side + 1
				flag = 0
				while l <= r:
					mid = (l + r) // 2
					summ = a[i + side - 1][mid + side - 1] - a[i + side - 1][mid - 1] - a[i - 1][mid + side - 1] + a[i - 1][mid - 1]
					if summ >= val * side * side:
						r = mid - 1
						p = mid
						flag = 1
					else:
						l = mid + 1
				if flag == 1:
					ans += m - side - p + 2
		print(ans)
	calculate()


def matrix_fun(matrix, n, m, k, f):
	count = 0
	a = min(n, m)
	while f < a + 1:
		i = f
		j = m
		while i < n + 1:
			x = i - f + 1
			y = j - f + 1
			z = abs(matrix[i][j] - matrix[x - 1][j] - matrix[i][y - 1] + matrix[x - 1][y - 1])
			if z // (f * f) < k:
				i += 1
			else:
				start = f
				end = m
				while start <= end:
					mid = (start + end) // 2
					x = i - f + 1
					y = mid - f + 1
					z = matrix[i][mid] - matrix[x - 1][mid] - matrix[i][y - 1] + matrix[x - 1][y - 1]
					if z // (f * f) < k:
						start = mid + 1
					else:
						c = mid
						end = mid - 1
				count += m - c + 1
				i += 1
		f += 1
	return count
t = int(input())
for _ in range(t):
	(R, C, k) = map(int, input().split())
	matrix = []
	for i in range(R):
		a = list(map(int, input().split()))
		matrix.append(a)
	for i in range(R):
		sum = 0
		for j in range(C):
			sum += matrix[i][j]
			matrix[i][j] = sum
	for i in range(C):
		sum = 0
		for j in range(R):
			sum += matrix[j][i]
			matrix[j][i] = sum
	for i in matrix:
		i.insert(0, 0)
	b = []
	for i in range(C + 1):
		b.append(0)
	matrix.insert(0, b)
	print(matrix_fun(matrix, R, C, k, 1))


def solve():
	(m, n, k) = map(int, input().split())
	v = []
	for i in range(0, m):
		v.append([int(j) for j in input().split()])
	summ = [[0 for i in range(n)] for j in range(m)]
	for i in range(m):
		summ[i][0] = v[i][0]
		for j in range(1, n):
			summ[i][j] = summ[i][j - 1] + v[i][j]
	for j in range(n):
		for i in range(1, m):
			summ[i][j] += summ[i - 1][j]
	count = 0
	size_up = min(n, m)
	for size in range(1, size_up + 1):
		for i in range(m - size + 1):
			low = 0
			high = n - size
			while low <= high:
				mid = (low + high) // 2
				total = summ[i + size - 1][mid + size - 1]
				if i > 0:
					total -= summ[i - 1][mid + size - 1]
				if mid > 0:
					total -= summ[i + size - 1][mid - 1]
				if i > 0 and mid > 0:
					total += summ[i - 1][mid - 1]
				avg = total * 1.0 / (size * size)
				if avg >= k:
					high = mid - 1
				else:
					low = mid + 1
			if high + 1 <= n - size:
				high += 1
				count += n - size - high + 1
	return count
t = int(input())
for z in range(t):
	ans = solve()
	print(ans)


t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	a = []
	for i in range(n):
		b = list(map(int, input().split()))
		a.append(b)
	psm = [[0 for i in range(m)] for j in range(n)]
	psm[0][0] = a[0][0]
	for i in range(1, m):
		psm[0][i] = psm[0][i - 1] + a[0][i]
	for i in range(1, n):
		psm[i][0] = psm[i - 1][0] + a[i][0]
	for i in range(1, n):
		for j in range(1, m):
			psm[i][j] = psm[i - 1][j] + psm[i][j - 1] - psm[i - 1][j - 1] + a[i][j]
	data = 0
	sab = n
	for i in range(n):
		mc = 1
		for j in range(m):
			for t in range(max(mc, 1), sab + 1):
				if t - 1 <= i and t - 1 <= j:
					s = 0
					if i == t - 1 or j == t - 1:
						if i == t - 1 and j == t - 1:
							s = psm[i][j]
						elif i == t - 1:
							s = psm[i][j] - psm[i][j - t]
						else:
							s = psm[i][j] - psm[i - t][j]
					else:
						s = psm[i][j] - psm[i - t][j] - psm[i][j - t] + psm[i - t][j - t]
					if s >= t * t * k:
						data += m - j
						mc = t + 1
					else:
						break
	print(data)


def precomputed(matrix):
	dp = [[0 for j in range(len(matrix[0]))] for i in range(len(matrix))]
	for i in range(0, len(matrix)):
		for j in range(0, len(matrix[0])):
			dp[i][j] = 0
	dp[0][0] = matrix[0][0]
	for j in range(1, len(matrix[0])):
		dp[0][j] = matrix[0][j] + dp[0][j - 1]
	for i in range(1, len(matrix)):
		dp[i][0] = matrix[i][0] + dp[i - 1][0]
	for i in range(1, len(matrix)):
		for j in range(1, len(matrix[0])):
			dp[i][j] = matrix[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
	return dp

def calculateno(precompmat, matrix, count, k):
	dsarr = 2
	while dsarr <= len(matrix):
		matrixno = dsarr - 1
		for i in range(dsarr - 1, len(matrix)):
			target = k * pow(dsarr, 2)
			pos = binarysearchpos(matrix[i], target, dsarr - 1, precompmat, matrixno)
			if pos == -1:
				count += 0
			else:
				count += len(matrix[0]) - pos
			matrixno += 1
		dsarr += 1
	return count

def countSquares(m, n):
	if n < m:
		temp = m
		m = n
		n = temp
	return m * (m + 1) * (2 * m + 1) / 6 + (n - m) * m * (m + 1) / 2

def binarysearchpos(arr, k, start, matrix, cols):
	x = len(matrix[0]) - 1
	(leftmove, rightmove) = (start + 1, cols)
	if x - leftmove >= 0 and rightmove - leftmove >= 0:
		value = matrix[cols][-1] - matrix[cols][x - leftmove] - matrix[rightmove - leftmove][x] + matrix[rightmove - leftmove][x - leftmove]
	elif x - leftmove >= 0:
		value = matrix[cols][-1] - matrix[cols][x - leftmove]
	elif rightmove - leftmove >= 0:
		value = matrix[cols][-1] - matrix[rightmove - leftmove][x]
	else:
		value = matrix[cols][-1]
	if value < k:
		return -1
	else:
		end = len(arr) - 1
		x = len(matrix[0]) - 1
		(leftmove, rightmove) = (start + 1, cols)
		while start < end:
			mid = start + (end - start) // 2
			if mid - leftmove >= 0 and rightmove - leftmove >= 0:
				value = matrix[cols][mid] - matrix[cols][mid - leftmove] - matrix[rightmove - leftmove][mid] + matrix[rightmove - leftmove][mid - leftmove]
			elif mid - leftmove >= 0:
				value = matrix[cols][mid] - matrix[cols][mid - leftmove]
			elif rightmove - leftmove >= 0:
				value = matrix[cols][mid] - matrix[rightmove - leftmove][mid]
			else:
				value = matrix[cols][mid]
			if value >= k:
				end = mid
			else:
				start = mid + 1
		return end
for i in range(0, 10):
	i = 10
t = int(input())
while t > 0:
	temp = list(map(int, input().split()))
	(N, M, K) = (temp[0], temp[1], temp[2])
	(matrix, norow) = ([], N)
	while norow:
		arr = list(map(int, input().split()))
		matrix.append(arr)
		norow -= 1
	if K == 0:
		finalans = countSquares(M, N)
		print(int(finalans))
		t -= 1
		continue
	count = 0
	for i in range(0, N):
		for j in range(0, M):
			if matrix[i][j] >= K:
				count += 1
	precompmat = precomputed(matrix)
	finalans = calculateno(precompmat, matrix, count, K)
	for i in range(0, 10):
		i = 10
	print(finalans)
	t -= 1


def main():
	t = int(input())
	while t:
		(m, n, k) = map(int, input().strip().split(' '))
		matrix = [[0 for x in range(n)] for y in range(m)]
		matrix = []
		for i in range(m):
			r = list(map(int, input().strip().split(' ')))
			matrix.append(r)
		aux = [[0 for x in range(n + 1)] for y in range(m + 1)]
		for i in range(m + 1):
			aux[i][0] = 0
		for j in range(n + 1):
			aux[0][j] = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				aux[i][j] = matrix[i - 1][j - 1]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				aux[i][j] += aux[i][j - 1]
		for j in range(1, n + 1):
			for i in range(1, m + 1):
				aux[i][j] += aux[i - 1][j]
		count = 0
		for p in range(1, m + 1):
			for i in range(1, m - p + 2):
				l = 1
				h = n - p + 1
				mid = 0
				q = 0
				flag = 0
				while l <= h:
					mid = int((l + h) / 2)
					ans = aux[i + p - 1][mid + p - 1] - aux[i + p - 1][mid - 1] - aux[i - 1][mid + p - 1] + aux[i - 1][mid - 1]
					if ans >= k * p * p:
						h = mid - 1
						q = mid
						flag = 1
					else:
						l = mid + 1
				if flag == 1:
					count += n - p - q + 2
		print(count)
		t -= 1
main()


from sys import stdin, stdout, setrecursionlimit

def binarySearch(lr, l, h, i, cnt):
	if l <= h:
		mid = (l + h) // 2
		val = lr[i][mid]
		if i - cnt >= 0 and mid - cnt >= 0:
			val = val - lr[i - cnt][mid] - lr[i][mid - cnt] + lr[i - cnt][mid - cnt]
		elif i - cnt >= 0:
			val -= lr[i - cnt][mid]
		elif mid - cnt >= 0:
			val -= lr[i][mid - cnt]
		if val / (cnt * cnt) >= k:
			ind = binarySearch(lr, l, mid - 1, i, cnt)
			return min(mid, ind) if ind != -1 else mid
		else:
			return binarySearch(lr, mid + 1, h, i, cnt)
	else:
		return -1
t = int(stdin.readline())
for _ in range(t):
	(n, m, k) = map(int, stdin.readline().strip().split())
	a = []
	lr = []
	for i in range(n):
		arr = list(map(int, stdin.readline().strip().split()))
		a.append(arr)
		lr.append(arr[:])
	count = 0
	for i in range(n):
		for j in range(m):
			if i == 0 and j > 0:
				lr[i][j] += lr[i][j - 1]
			if j == 0 and i > 0:
				lr[i][j] += lr[i - 1][j]
			if a[i][j] >= k:
				count += 1
	for i in range(1, n):
		for j in range(1, m):
			lr[i][j] += lr[i][j - 1] + lr[i - 1][j] - lr[i - 1][j - 1]
	for cnt in range(2, n + 1):
		for i in range(cnt - 1, n):
			val = lr[i][m - 1]
			if i - cnt >= 0 and m - 1 - cnt >= 0:
				val = val - lr[i - cnt][m - 1] - lr[i][m - 1 - cnt] + lr[i - cnt][m - 1 - cnt]
			elif i - cnt >= 0:
				val = val - lr[i - cnt][m - 1]
			elif m - 1 - cnt >= 0:
				val = val - lr[i][m - 1 - cnt]
			if val / (cnt * cnt) >= k:
				l = cnt - 1
				h = m - 1
				ind = binarySearch(lr, l, h, i, cnt)
				if ind > -1:
					count += m - ind
	print(count)


def fun(l, n, m, k, order):
	count = 0
	minimum = min(n, m)
	while order < minimum + 1:
		i = order
		j = m
		while i < n + 1:
			x = i - order + 1
			y = j - order + 1
			z = l[i][j] - l[x - 1][j] - l[i][y - 1] + l[x - 1][y - 1]
			if z / (order * order) < k:
				i += 1
			else:
				start = order
				end = m
				while start <= end:
					mid = (start + end) // 2
					x = i - order + 1
					y = mid - order + 1
					z = l[i][mid] - l[x - 1][mid] - l[i][y - 1] + l[x - 1][y - 1]
					if z / (order * order) < k:
						start = mid + 1
					else:
						ans = mid
						end = mid - 1
				count += m - ans + 1
				i += 1
		order += 1
	return count
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	l = []
	l.append([0] * (m + 1))
	for _ in range(n):
		a = [0] + list(map(int, input().split()))
		l.append(a)
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			l[i][j] += l[i][j - 1]
	for j in range(1, m + 1):
		for i in range(1, n + 1):
			l[i][j] += l[i - 1][j]
	ans = fun(l, n, m, k, 1)
	print(ans)


def row_sum(s, n, m):
	for i in range(n + 1):
		back = 0
		for j in range(m + 1):
			s[i][j] += back
			back = s[i][j]
	return s

def col_sum(s, n, m):
	for j in range(m + 1):
		back = 0
		for i in range(n + 1):
			s[i][j] += back
			back = s[i][j]
	return s

def fun(s, n, m):
	return

def solve():
	(n, m, k) = map(int, input().split())
	a = []
	s = []
	ans = 0
	for x in range(n):
		a.append([int(y) for y in input().split()])
	s.append([])
	if k == 'kdjflkdf':
		return
	if k == 'kdjflkdf':
		return
	if k == 'kdjflkdf':
		return
	for i in range(n + 1):
		for j in range(m + 1):
			if i == 0:
				s[i].append(0)
			elif j == 0:
				s.append([0])
			else:
				s[i].append(a[i - 1][j - 1])
	s = row_sum(s, n, m)
	s = col_sum(s, n, m)
	mi = min(n, m)
	if k == 'kdjflkdf':
		return
	if k == 'kdjflkdf':
		return
	if k == 'kdjflkdf':
		return
	for curr in range(1, mi + 1):
		first = curr
		end = m
		while first >= 1 and first <= n and (end >= 1) and (end <= m):
			if (s[first][end] - s[first - curr][end] - s[first][end - curr] + s[first - curr][end - curr]) / (curr * curr) >= k:
				ans += n - first + 1
				end -= 1
			else:
				first += 1
	print(ans)
for _ in range(int(input())):
	solve()


def average(mat, l, i, j):
	ans = (mat[i][j] + mat[i - l][j - l] - mat[i - l][j] - mat[i][j - l]) / (l * l)
	return ans
T = int(input())
for t in range(T):
	(n, m, k) = map(int, input().split())
	A = [[0] * (m + 1)]
	for i in range(n):
		A.append([0] + list(map(int, input().split())))
	(B, C) = ([], [])
	for i in range(n + 1):
		B.append([])
		C.append([])
		for j in range(m + 1):
			B[i].append(A[i][j])
			C[i].append(10 ** 9 + 1)
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			B[i][j] = B[i][j] + B[i][j - 1]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			B[i][j] = B[i][j] + B[i - 1][j]
	score = 0
	for i in range(1, n + 1):
		mx = min(i, m)
		mn = 1
		while mx >= mn:
			mid = (mx + mn) // 2
			if average(B, mid, i, m) >= k:
				mn = mid + 1
			else:
				mx = mid - 1
		score += (mx + mn) // 2
		C[i][m] = (mx + mn) // 2
	for j in range(1, m):
		mx = min(n, j)
		mn = 1
		while mx >= mn:
			mid = (mx + mn) // 2
			if average(B, mid, n, j) >= k:
				mn = mid + 1
			else:
				mx = mid - 1
		score += (mx + mn) // 2
		C[n][j] = (mx + mn) // 2
	for i in range(n - 1, 0, -1):
		for j in range(m - 1, 0, -1):
			c = min(C[i + 1][j], C[i][j + 1])
			temp = min(i, j)
			c = min(temp, c)
			while c > 0 and average(B, c, i, j) < k:
				c -= 1
			score += c
			C[i][j] = c
	print(score)


def solve(A, n, m, k):
	if k == 0:
		count = 0
		for l in range(1, n + 1):
			count += (n - l + 1) * (m - l + 1)
		return count
	APS = [[0] * (m + 1), [0] * (m + 1)]
	APS[1][1] = A[0][0]
	for i in range(2, m + 1):
		APS[1][i] = APS[1][i - 1] + A[0][i - 1]
	for i in range(2, n + 1):
		APS.append([0] * (m + 1))
		APS[i][1] = APS[i - 1][1] + A[i - 1][0]
		for j in range(2, m + 1):
			APS[i][j] = APS[i - 1][j] + APS[i][j - 1] - APS[i - 1][j - 1] + A[i - 1][j - 1]
	count = 0
	for l in range(1, n + 1):
		lsq = l * l
		top = n - l + 1
		left = 1
		prevTop = n - l + 2
		sizeCount = 0
		i = 0
		while top > 0 and left < m - l + 2:
			while left < m - l + 2:
				s = APS[top + l - 1][left + l - 1] - APS[top - 1][left + l - 1] - APS[top + l - 1][left - 1] + APS[top - 1][left - 1]
				if s >= lsq * k:
					break
				left += 1
			if s < lsq * k:
				break
			while top > 1:
				s = APS[top + l - 2][left + l - 1] - APS[top - 2][left + l - 1] - APS[top + l - 2][left - 1] + APS[top - 2][left - 1]
				if s < lsq * k:
					break
				top -= 1
			sizeCount += (prevTop - top) * (m - left - l + 2)
			prevTop = top
			top -= 1
			i += 1
		count += sizeCount
	return count
t = int(input())
for tc in range(t):
	(n, m, k) = map(int, input().split())
	A = []
	for i in range(n):
		A.append(list(map(int, input().split())))
	result = solve(A, n, m, k)
	print(result)


DEBUG = False

def solve(A, n, m, k):
	if k == 0:
		count = 0
		for l in range(1, n + 1):
			count += (n - l + 1) * (m - l + 1)
		return count
	APS = [[0] * (m + 1), [0] * (m + 1)]
	APS[1][1] = A[0][0]
	for i in range(2, m + 1):
		APS[1][i] = APS[1][i - 1] + A[0][i - 1]
	for i in range(2, n + 1):
		APS.append([0] * (m + 1))
		APS[i][1] = APS[i - 1][1] + A[i - 1][0]
		for j in range(2, m + 1):
			APS[i][j] = APS[i - 1][j] + APS[i][j - 1] - APS[i - 1][j - 1] + A[i - 1][j - 1]
	count = 0
	for l in range(1, n + 1):
		lsq = l * l
		top = n - l + 1
		left = 1
		prevTop = n - l + 2
		sizeCount = 0
		i = 0
		while top > 0 and left < m - l + 2:
			while left < m - l + 2:
				s = APS[top + l - 1][left + l - 1] - APS[top - 1][left + l - 1] - APS[top + l - 1][left - 1] + APS[top - 1][left - 1]
				if s >= lsq * k:
					break
				left += 1
			if s < lsq * k:
				break
			while top > 1:
				s = APS[top + l - 2][left + l - 1] - APS[top - 2][left + l - 1] - APS[top + l - 2][left - 1] + APS[top - 2][left - 1]
				if s < lsq * k:
					break
				top -= 1
			sizeCount += (prevTop - top) * (m - left - l + 2)
			prevTop = top
			top -= 1
			i += 1
		count += sizeCount
	return count
if DEBUG:
	f = open('tests/KAVGMAT-tests.txt', 'r')
	t = int(f.readline())
	for tc in range(t):
		(n, m, k) = map(int, f.readline().split())
		A = []
		for i in range(n):
			A.append(list(map(int, f.readline().split())))
		result = solve(A, n, m, k)
		print(result)
else:
	t = int(input())
	for tc in range(t):
		(n, m, k) = map(int, input().split())
		A = []
		for i in range(n):
			A.append(list(map(int, input().split())))
		result = solve(A, n, m, k)
		print(result)


def fun(mat, n, m, k, order):
	cnt = 0
	Min = min(n, m)
	while order < Min + 1:
		i = order
		j = m
		while i < n + 1:
			x = i - order + 1
			y = j - order + 1
			z = mat[i][j] - mat[x - 1][j] - mat[i][y - 1] + mat[x - 1][y - 1]
			if z / order ** 2 < k:
				i += 1
			else:
				start = order
				end = m
				while start <= end:
					mid = (start + end) // 2
					x = i - order + 1
					y = mid - order + 1
					z = mat[i][mid] - mat[x - 1][mid] - mat[i][y - 1] + mat[x - 1][y - 1]
					if z / order ** 2 < k:
						start = mid + 1
					else:
						ans = mid
						end = mid - 1
				cnt += m - ans + 1
				i += 1
		order += 1
	return cnt
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	mat = []
	for _ in range(n):
		mat.append(list(map(int, input().split())))
	for i in range(n):
		s = 0
		for j in range(m):
			s += mat[i][j]
			mat[i][j] = s
	for i in range(m):
		s = 0
		for j in range(n):
			s += mat[j][i]
			mat[j][i] = s
	for i in range(n):
		mat[i].insert(0, 0)
	t = len(mat[0])
	l = [0 for _ in range(t)]
	mat.insert(0, l)
	print(fun(mat, n, m, k, 1))


import sys

def get_int():
	return int(sys.stdin.readline().strip())

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def p_int(x):
	sys.stdout.write(str(x) + '\n')

def solve():
	(n, m, K) = get_ints()
	arr = [[0 for ii in range(m + 1)] for jj in range(n + 1)]
	for i in range(n):
		temp = get_array()
		for j in range(m):
			arr[i + 1][j + 1] = temp[j]
	for i in range(n + 1):
		for j in range(1, m + 1):
			arr[i][j] += arr[i][j - 1]
	for i in range(m + 1):
		for j in range(1, n + 1):
			arr[j][i] += arr[j - 1][i]

	def good(i, j, k, K):
		k += 1
		cnt = k * k
		pref = arr[i + k][j + k] - arr[i][j + k] - arr[i + k][j] + arr[i][j]
		return pref / cnt >= K
	res = 0
	x = min(n, m)
	for k in range(x):
		i = n - 1 - k
		j = 0
		while i >= 0 and j < m - k:
			temp = 0
			if good(i, j, k, K):
				temp = m - j - k
				i -= 1
			else:
				j += 1
			res += temp
	p_int(res)
t = get_int()
for _ in range(t):
	solve()


def kavgmat(n, m, matrix):
	sum_matrix = [[0 for _ in range(m)] for _ in range(n)]
	sum_matrix[0][0] = matrix[0][0]
	for i in range(1, m):
		sum_matrix[0][i] = sum_matrix[0][i - 1] + matrix[0][i]
	for i in range(1, n):
		sum_matrix[i][0] = sum_matrix[i - 1][0] + matrix[i][0]
	for i in range(1, n):
		for j in range(1, m):
			sum_matrix[i][j] = sum_matrix[i - 1][j] + sum_matrix[i][j - 1] + matrix[i][j] - sum_matrix[i - 1][j - 1]
	temp_matrix = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			temp_matrix[i][j] = sum_matrix[i - 1][j - 1]
	sum_matrix = temp_matrix
	answer = 0
	square_sum = lambda x, y, size: sum_matrix[x][y] - sum_matrix[x][y - size] - sum_matrix[x - size][y] + sum_matrix[x - size][y - size]
	for i in range(n):
		for j in range(m):
			if matrix[i][j] >= 0:
				answer += 1
	for size in range(2, n + 1):
		for i in range(size, n + 1):
			if square_sum(i, size, size) < 0:
				continue
			elif not square_sum(i, -1, size) < 0:
				answer += m - size + 1
				continue
			else:
				start = size
				end = m
				while start < end - 1:
					mid = (start + end) // 2
					if square_sum(i, mid, size) >= 0:
						start = mid
					else:
						end = mid
				answer += start - size + 1
	return answer
t = int(input())
while t:
	(n, m, k) = map(int, input().split())
	matrix = [[None for _ in range(m)] for _ in range(n)]
	for i in range(1, n + 1):
		matrix[-i] = [a - k for a in reversed(list(map(int, input().split())))]
	print(kavgmat(n, m, matrix))
	t -= 1


def printMatrix(M):
	for a in M:
		for b in a:
			print(b, end=' ')
		print()
	print()

def getColumn(A, row, m, K, size):
	(start, end) = (size, m)
	minCol = end + 1
	while start <= end:
		mid = (start + end) // 2
		(r2, c2) = (row, mid)
		(r1, c1) = (row - size + 1, mid - size + 1)
		if getRangeSum(A, r1, c1, r2, c2) / (size * size) >= K:
			minCol = mid
			end = mid - 1
		else:
			start = mid + 1
	return minCol

def getCount(A, N, M, K, size):
	s = 0
	Row = getRow(A, N, M, K, size)
	for row in range(Row, N + 1):
		col = getColumn(A, row, M, K, size)
		s += M - col + 1
	return s

def getRow(A, n, m, K, size):
	for row in range(size, n + 1):
		(r2, c2) = (row, m)
		(c1, r1) = (m - size + 1, row - size + 1)
		if getRangeSum(A, r1, c1, r2, c2) / (size * size) >= K:
			return row
	return n

def putZeroes(A, n, m):
	M = [[0 for x in range(m + 1)] for y in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			M[i][j] = A[i - 1][j - 1]
	return M

def getRangeSum(A, r1, c1, r2, c2):
	s = A[r2][c2] + A[r1 - 1][c1 - 1] - A[r1 - 1][c2] - A[r2][c1 - 1]
	return s

def getPresum(A, n, m):
	P = [[0 for i in range(m)] for y in range(n)]
	for i in range(n):
		for j in range(m):
			if i == 0:
				P[i][j] = P[i][j - 1] + A[i][j]
			elif j == 0:
				P[i][j] = P[i - 1][j] + A[i][j]
	for i in range(1, n):
		for j in range(1, m):
			P[i][j] = A[i][j] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1]
	return P
for t in range(int(input())):
	(N, M, K) = map(int, input().split())
	Mat = []
	for i in range(N):
		Mat.append(list(map(int, input().split())))
	COUNT = 0
	Mat = getPresum(Mat, N, M)
	Mat = putZeroes(Mat, N, M)
	for size in range(1, N + 1):
		s = getCount(Mat, N, M, K, size)
		COUNT += s
	print(COUNT)


from sys import stdin
for _ in range(int(stdin.readline())):
	(n, m, k) = [int(x) for x in stdin.readline().split()]
	arr = [None] * n
	for i in range(n):
		arr[i] = [int(x) for x in stdin.readline().split()]
	pre = [[0 for _ in range(m)] for _ in range(n)]
	pre[0][0] = arr[0][0]
	for i in range(1, n):
		pre[i][0] = pre[i - 1][0] + arr[i][0]
	for i in range(1, m):
		pre[0][i] += pre[0][i - 1] + arr[0][i]
	for r in range(1, n):
		for c in range(1, m):
			pre[r][c] = pre[r - 1][c] + pre[r][c - 1] + arr[r][c]
			pre[r][c] -= pre[r - 1][c - 1]
	ans = 0
	for j in range(min(n, m)):
		(r, c) = (j, m - 1)
		while r < n and c >= j:
			if j == 0:
				if arr[r][c] >= k:
					ans += n - r
					c -= 1
				else:
					r += 1
			else:
				(a, b) = (r - j, c - j)
				val = pre[r][c]
				if b > 0:
					val -= pre[r][b - 1]
				if a > 0:
					val -= pre[a - 1][c]
				if a > 0 and b > 0:
					val += pre[a - 1][b - 1]
				q = (j + 1) * (j + 1)
				val //= q
				if val >= k:
					ans += n - r
					c -= 1
				else:
					r += 1
	print(ans)


import sys
input = sys.stdin.readline

def solve():
	(n, m, k) = map(int, input().split())
	dp = [[0 for i in range(m + 1)]]
	for i in range(n):
		dp.append([0] + list(map(int, input().split())))
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
	ans = 0
	for q in range(min(n, m), 0, -1):
		for i in range(n, q - 1, -1):
			(l, r) = (q, m)
			index = -1
			while l <= r:
				j = l + (r - l) // 2
				(i1, j1, i2, j2) = (i - q, j - q, i, j)
				s = dp[i2][j2] - dp[i2][j1] - dp[i1][j2] + dp[i1][j1]
				if s / q ** 2 >= k:
					index = j
					r = j - 1
				else:
					l = j + 1
			if index != -1:
				ans += m - index + 1
	print(ans)
for t in range(int(input())):
	solve()


import sys
input = sys.stdin.readline

def fxn(mat, n, m, k, o):
	cnt = 0
	mn = min(n, m)
	while o < mn + 1:
		(i, j) = (o, m)
		while i < n + 1:
			x = i - o + 1
			y = j - o + 1
			z = mat[i][j] - mat[x - 1][j] - mat[i][y - 1] + mat[x - 1][y - 1]
			if z / (o * o) < k:
				i += 1
			else:
				(st, ed) = (o, m)
				while st <= ed:
					mid = (st + ed) // 2
					x = i - o + 1
					y = mid - o + 1
					z = mat[i][mid] - mat[x - 1][mid] - mat[i][y - 1] + mat[x - 1][y - 1]
					if z / (o * o) < k:
						st = mid + 1
					else:
						ans = mid
						ed = mid - 1
				cnt += m - ans + 1
				i += 1
		o += 1
	return cnt

def solve():
	(n, m, k) = map(int, input().split())
	mat = []
	(rows, cols) = (n + 1, m + 1)
	matrix = [[0] * cols for i in range(rows)]
	for i in range(n):
		mat.append(list(map(int, input().split())))
	for i in range(1, n + 1):
		sm = 0
		for j in range(1, m + 1):
			sm += mat[i - 1][j - 1]
			matrix[i][j] = sm
	for i in range(1, m + 1):
		sm = 0
		for j in range(1, n + 1):
			sm += matrix[j][i]
			matrix[j][i] = sm
	Ans = fxn(matrix, n, m, k, 1)
	print(Ans)
for _ in range(int(input())):
	solve()


T = int(input())
for _ in range(T):
	(N, M, K) = map(int, input().split())
	lst = []
	l = [0] * (M + 1)
	lst.append(l)
	for i in range(N):
		arr = list(map(int, input().split()))
		arr.insert(0, 0)
		for j in range(1, M + 1):
			arr[j] = arr[j] + arr[j - 1]
		lst.append(arr)
	for i in range(2, N + 1):
		for j in range(1, M + 1):
			lst[i][j] += lst[i - 1][j]
	mini = min(N, M)
	count = 0
	order = 1
	while order <= mini:
		i = order
		j = M
		while i <= N:
			x = i - order + 1
			y = j - order + 1
			total = lst[i][j] - lst[x - 1][j] - lst[i][y - 1] + lst[x - 1][y - 1]
			if total / (order * order) < K:
				i += 1
			else:
				low = order
				high = M
				index = 0
				while low <= high:
					mid = (low + high) // 2
					x = i - order + 1
					y = mid - order + 1
					total = lst[i][mid] - lst[x - 1][mid] - lst[i][y - 1] + lst[x - 1][y - 1]
					if total / (order * order) < K:
						low = mid + 1
					else:
						index = mid
						high = mid - 1
				count += M - index + 1
				i += 1
		order += 1
	print(count)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	matrix = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(1, n + 1):
		l = list(map(int, input().split()))
		for j in range(m):
			matrix[i][j + 1] = l[j] + matrix[i][j] + matrix[i - 1][j + 1] - matrix[i - 1][j]
	ans = 0
	for order in range(1, n + 1):
		for raw in range(order, n + 1):
			value = matrix[raw][m] - matrix[raw][m - order] - matrix[raw - order][m] + matrix[raw - order][m - order]
			if value / (order * order) < k:
				continue
			else:
				start = order
				end = m
				index = m + 1
				while start <= end:
					mid = (start + end) // 2
					value = matrix[raw][mid] - matrix[raw][mid - order] - matrix[raw - order][mid] + matrix[raw - order][mid - order]
					if value / (order * order) < k:
						start = mid + 1
					else:
						end = mid - 1
						index = mid
				ans += m - index + 1
	print(ans)


def func(mat, i, j, lo, rs, k):
	corner = mat[i][j]
	backone = mat[i - lo - 1][j]
	backtwo = mat[i][j - lo - 1]
	remains = mat[i - lo - 1][j - lo - 1]
	store = corner - backone - backtwo + remains
	if store - k * rs >= 0:
		return True
	return False
for v in range(int(input())):
	(n, m, k) = map(int, input().split())
	mat = [[0] * (m + 1)]
	for i in range(n):
		mat.append([0] + list(map(int, input().split())))
	temp = [[0 for g in range(m + 1)] for y in range(n + 1)]
	for j in range(1, m + 1):
		for i in range(1, n + 1):
			temp[i][j] = temp[i - 1][j] + temp[i][j - 1] - temp[i - 1][j - 1] + mat[i][j]
	mat = temp
	nums = 0
	lo = 0
	if n <= m:
		fans = n
	else:
		fans = m
	while lo < fans:
		rs = (lo + 1) ** 2
		i = lo + 1
		while i < n + 1:
			low = lo + 1
			high = m
			while low <= high:
				mid = low + (high - low + 1) // 2
				testcharge = func(mat, i, mid, lo, rs, k)
				if testcharge:
					high = mid - 1
				else:
					low = mid + 1
			nums += 1 + m - low
			i += 1
		lo += 1
	print(nums)


def prefixTable(table, dp, n, m):
	dp[0][0] = table[0][0]
	for j in range(1, m):
		dp[0][j] = table[0][j] + dp[0][j - 1]
	for i in range(1, n):
		dp[i][0] = table[i][0] + dp[i - 1][0]
	for i in range(1, n):
		for j in range(1, m):
			dp[i][j] = table[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
for i in range(int(input())):
	(n, m, k) = list(map(int, input().split()))
	table = []
	for i in range(n):
		row = list(map(int, input().split()))
		table.append(row)
	dp = [[0 for i in range(m)] for j in range(n)]
	prefixTable(table, dp, n, m)
	dp.insert(0, [0] * m)
	for i in dp:
		i.insert(0, 0)
	mini = min(n, m)
	total = 0
	for window in range(0, mini):
		for j in range(window + 1, n + 1):
			start = window + 1
			end = m
			ans = m + 1
			while start <= end:
				mid = (start + end) // 2
				x = j - (window + 1)
				y = mid - (window + 1)
				avg = (dp[j][mid] - dp[x][mid] - dp[j][y] + dp[x][y]) / ((window + 1) * (window + 1))
				if avg < k:
					start = mid + 1
				elif avg >= k:
					ans = mid
					end = mid - 1
			total += m - ans + 1
	print(total)


def fun(mat, N, M, K, order):
	count = 0
	mini = min(N, M)
	while order < mini + 1:
		i = order
		j = M
		while i < N + 1:
			x = i - order + 1
			y = j - order + 1
			z = mat[i][j] - mat[x - 1][j] - mat[i][y - 1] + mat[x - 1][y - 1]
			checked = z / (order * order)
			if checked < K:
				i += 1
			else:
				start = order
				end = M
				while start <= end:
					mid = int(end + (start - end) / 2)
					x = i - order + 1
					y = mid - order + 1
					z = mat[i][mid] - mat[x - 1][mid] - mat[i][y - 1] + mat[x - 1][y - 1]
					checked = z / (order * order)
					if checked < K:
						start = mid + 1
					else:
						ans = mid
						end = mid - 1
				count += M - ans + 1
				i += 1
		order += 1
	return count
T = int(input())
for _ in range(T):
	(N, M, K) = map(int, input().split(' '))
	a = [0]
	mat = []
	mat.append([0] * (M + 1))
	for i in range(N):
		a = [0]
		a.extend(list(map(int, input().split(' '))))
		mat.append(a)
	for i in range(N + 1):
		pre = 0
		for j in range(M + 1):
			mat[i][j] += pre
			pre = mat[i][j]
	for j in range(M + 1):
		pre = 0
		for i in range(N + 1):
			pre += mat[i][j]
			mat[i][j] = pre
	ans = fun(mat, N, M, K, 1)
	print(ans)


def search(sum_a, n, m, k, order):
	count = 0
	minimum = min(n, m)
	while order < minimum + 1:
		i = order
		j = m
		while i < n + 1:
			x = i - order + 1
			y = j - order + 1
			z = sum_a[i][j] - sum_a[x - 1][j] - sum_a[i][y - 1] + sum_a[x - 1][y - 1]
			if z / (order * order) < k:
				i += 1
			else:
				start = order
				end = m + 1
				ans = m + 1
				while start <= end:
					mid = (start + end) // 2
					x = i - order + 1
					y = mid - order + 1
					z = sum_a[i][mid] - sum_a[x - 1][mid] - sum_a[i][y - 1] + sum_a[x - 1][y - 1]
					if z / (order * order) < k:
						start = mid + 1
					else:
						ans = mid
						end = mid - 1
				count += m - ans + 1
				i += 1
		order += 1
	return count
t = int(input())
for _ in range(t):
	(n, m, kc) = map(int, input().split(' '))
	arr = []
	ab = [0 for _ in range(m + 1)]
	arr.append(ab)
	for _ in range(n):
		a = list(map(int, input().split(' ')))[:m]
		a.insert(0, 0)
		arr.append(a)
	ans = 0
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			arr[i][j] += arr[i][j - 1]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			arr[i][j] += arr[i - 1][j]
	ans = search(arr, n, m, kc, 1)
	print(ans)


import itertools
import math

def binaryRow(arr, k, start, n):
	eles = n * n
	low = start
	high = len(arr) - 1
	lastPossible = -1
	while low <= high:
		mid = (low + high) // 2
		val = arr[mid][-1] - arr[mid - n][-1] - arr[mid][-(1 + n)] + arr[mid - n][-(1 + n)]
		if val / eles < k:
			mid = low + 1
		else:
			lastPossible = high
			mid = high - 1
	return lastPossible

def binaryCol(arr, k, start, n, row):
	eles = n * n
	low = start
	high = len(arr[0]) - 1
	lastPossible = -1
	while low <= high:
		mid = (low + high) // 2
		val = arr[row][mid] - arr[row - n][mid] - arr[row][mid - n] + arr[row - n][mid - n]
		if val / eles < k:
			low = mid + 1
		else:
			lastPossible = mid
			high = mid - 1
	return lastPossible
t = int(input())
for _ in range(t):
	(n, m, k) = [int(i) for i in input().split()]
	mat = []
	mat2 = [[0 for i in range(m + 1)]]
	for i in range(n):
		line = [int(i) for i in input().split()]
		mat.append(line)
	for i in range(n):
		line = [0]
		for j in range(m):
			line.append(mat[i][j] + line[-1])
		mat2.append(line)
	for i in range(1, m + 1):
		for j in range(1, n + 1):
			mat2[j][i] += mat2[j - 1][i]
	res = 0
	for i in range(1, min(n, m) + 1):
		for j in range(i, n + 1):
			col = binaryCol(mat2, k, i, i, j)
			if col != -1:
				res += m + 1 - col
	print(res)


def solve(a, s, n, k):
	step = 1
	cntt = 0
	for x in range(2, n + 1):
		step += 1
		j = x
		for i in range(n, x - 1, -1):
			while j < m + 1:
				if (s[i][j] - s[i][j - step] - s[i - step][j] + s[i - step][j - step]) / (step * step) >= k:
					cntt += m + 1 - j
					break
				j += 1
	return cntt
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = [[0] * (n + 1)]
	for i in range(n):
		a.append([0] + list(map(int, input().split())))
	s = [[0] * (m + 1) for i in range(n + 1)]
	cnt = 0
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			s[i][j] = a[i][j] + s[i][j - 1]
			if a[i][j] >= k:
				cnt += 1
	for j in range(1, m + 1):
		for i in range(1, n + 1):
			s[i][j] = s[i][j] + s[i - 1][j]
	print(cnt + solve(a, s, n, k))


def solve_advanced(n, m, k, matrix):
	adv_matrix = [[0 for i in range(m + 1)] for j in range(n + 1)]
	for i in range(n):
		total1 = 0
		for j in range(m):
			total1 += matrix[i][j]
			adv_matrix[i + 1][j + 1] = total1 + adv_matrix[i][j + 1]
	total = 0
	for l in range(1, min(m, n) + 1):
		for i in range(n - l + 1):
			start = 0
			end = m - l
			idx = None
			while True:
				if end - start <= 1:
					mdl = end
					sm = adv_matrix[i + l][mdl + l] + adv_matrix[i][mdl] - adv_matrix[i + l][mdl] - adv_matrix[i][mdl + l]
					if sm / (l * l) >= k:
						idx = end
					mdl = start
					sm = adv_matrix[i + l][mdl + l] + adv_matrix[i][mdl] - adv_matrix[i + l][mdl] - adv_matrix[i][mdl + l]
					if sm / (l * l) >= k:
						idx = start
					break
				else:
					mdl = (start + end) // 2
					sm = adv_matrix[i + l][mdl + l] + adv_matrix[i][mdl] - adv_matrix[i + l][mdl] - adv_matrix[i][mdl + l]
					if sm / (l * l) >= k:
						end = mdl
					else:
						start = mdl
			if idx != None:
				temp = m - l + 1 - idx
				total += temp
	return total
t = int(input())
for _ in range(t):
	(n, m, k) = [int(i) for i in input().split()]
	matrix = []
	for i in range(n):
		matrix.append([int(i) for i in input().split()])
	print(solve_advanced(n, m, k, matrix))


def minimum(n, m):
	if m < n:
		return m
	else:
		return n

def calculate(n, m, k, order, arr):
	count = 0
	min = minimum(n, m)
	while order < min + 1:
		i = order
		j = m
		while i < n + 1:
			x = i - order + 1
			y = j - order + 1
			z = arr[i][j] - arr[x - 1][j] - arr[i][y - 1] + arr[x - 1][y - 1]
			if z / (order * order) < float(k):
				i += 1
			else:
				start = order
				end = m
				while start <= end:
					mid = (start + end) // 2
					x = i - order + 1
					y = mid - order + 1
					z = arr[i][mid] - arr[x - 1][mid] - arr[i][y - 1] + arr[x - 1][y - 1]
					if z / (order * order) < float(k):
						start = mid + 1
					else:
						ans = mid
						end = mid - 1
				count += m - ans + 1
				i += 1
		order += 1
	return count

def solve(result):
	sum = 0
	linput = input().split()
	n = int(linput[0])
	m = int(linput[1])
	k = int(linput[2])
	arr = []
	for i in range(n):
		linput = input().split()
		row = []
		for j in range(m):
			row.append(int(linput[j]))
		arr.append(row)
	for i in range(n):
		sum = 0
		for j in range(m):
			sum += arr[i][j]
			arr[i][j] = sum
	for i in range(m):
		sum = 0
		for j in range(n):
			sum += arr[j][i]
			arr[j][i] = sum
	arr.insert(0, [0] * m)
	for i in range(n + 1):
		arr[i].insert(0, 0)
	result.append(calculate(n, m, k, 1, arr))
test = int(input())
result = []
for i in range(test):
	solve(result)
for i in range(test):
	print(result[i])


def findMaxSumSubMatrix(mat, z):
	(M, N) = (len(mat), len(mat[0]))
	sum = [[0 for x in range(N)] for y in range(M)]
	sum[0][0] = mat[0][0]
	for j in range(1, N):
		sum[0][j] = mat[0][j] + sum[0][j - 1]
	for i in range(1, M):
		sum[i][0] = mat[i][0] + sum[i - 1][0]
	for i in range(1, M):
		for j in range(1, N):
			sum[i][j] = mat[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]
	mi = min(M, N)
	count = 0
	for k in range(1, mi + 1):
		req = z * (k * k)
		for i in range(k - 1, M):
			ans = -1
			s = k - 1
			e = N - 1
			while s <= e:
				j = (s + e) // 2
				total = sum[i][j]
				if i - k >= 0:
					total = total - sum[i - k][j]
				if j - k >= 0:
					total = total - sum[i][j - k]
				if i - k >= 0 and j - k >= 0:
					total = total + sum[i - k][j - k]
				if total >= req:
					ans = j
					s = s
					e = j - 1
				else:
					s = j + 1
					e = e
			if ans != -1:
				count += N - ans
	return count
t = int(input())
for test in range(t):
	(n, m, z) = map(int, input().split())
	arr = []
	for i in range(n):
		temp = list(map(int, input().split()))
		arr.append(temp)
	ans = findMaxSumSubMatrix(arr, z)
	print(ans)


def auxc(a, n, m):
	w = [[0 for i in range(m + 1)] for j in range(n + 1)]
	for i in range(n):
		for j in range(1, m):
			a[i][j] += a[i][j - 1]
	for i in range(1, n):
		for j in range(m):
			a[i][j] += a[i - 1][j]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			w[i][j] = a[i - 1][j - 1]
	return w
hha = [[2, 2, 3], [4, 4, 5], [4, 5, 5]]

def bs(a, n, m, k):
	aux = auxc(a, n, m)
	ans = 0
	for s in range(1, n + 1):
		for i in range(1, n - s + 1 + 1):
			low = 1
			high = m - s + 1
			tem = 0
			ato = 0
			while low <= high:
				mid = (low + high) // 2
				sm = aux[i + s - 1][mid + s - 1] - aux[i + s - 1][mid - 1] - aux[i - 1][mid + s - 1] + aux[i - 1][mid - 1]
				if sm >= k * s * s:
					high = mid - 1
					tem = mid
					ato = 1
				else:
					low = mid + 1
			if ato == 1:
				ans += m - s - tem + 2
	return ans
t = int(input())
while t:
	(n, m, k) = map(int, input().split())
	a = []
	for i in range(n):
		tem = list(map(int, input().split()))
		a.append(tem)
	print(bs(a, n, m, k))
	t = t - 1


T = int(input())
for _ in range(T):
	(N, M, K) = map(int, input().split())
	A = []
	sum = []
	Ans = 0
	for x in range(N):
		A.append([int(y) for y in input().split()])
	sum.append([])
	for i in range(N + 1):
		for j in range(M + 1):
			if i == 0:
				sum[i].append(0)
			elif j == 0:
				sum.append([0])
			else:
				sum[i].append(A[i - 1][j - 1])
	for i in range(N + 1):
		prev = 0
		for j in range(M + 1):
			sum[i][j] += prev
			prev = sum[i][j]
	for j in range(M + 1):
		prev = 0
		for i in range(N + 1):
			sum[i][j] += prev
			prev = sum[i][j]
	Min = min(N, M)
	for ord in range(1, Min + 1):
		start = ord
		end = M
		while start >= 1 and start <= N and (end >= 1) and (end <= M):
			if (sum[start][end] - sum[start - ord][end] - sum[start][end - ord] + sum[start - ord][end - ord]) / (ord * ord) >= K:
				Ans += N - start + 1
				end -= 1
			else:
				start += 1
	print(Ans)


def func(matrix, N, M, K):
	count = 0
	minimum = min(N, M)
	for order in range(1, minimum + 1):
		for i in range(order, n + 1):
			j = M
			x = i - order + 1
			y = j - order + 1
			z = matrix[i][j] - matrix[x - 1][j] - matrix[i][y - 1] + matrix[x - 1][y - 1]
			if z // (order * order) < K:
				i += 1
			else:
				start = order
				end = M
				while start <= end:
					mid = (start + end) // 2
					x = i - order + 1
					y = mid - order + 1
					z = matrix[i][mid] - matrix[x - 1][mid] - matrix[i][y - 1] + matrix[x - 1][y - 1]
					if z // (order * order) < K:
						start = mid + 1
					else:
						ans = mid
						end = mid - 1
				count += M - ans + 1
		order += 1
	return count
try:
	for _ in range(int(input())):
		(n, m, k) = list(map(int, input().split()))
		matrix = []
		for i in range(n):
			matrix.append(list(map(int, input().split())))
		listColumn = [0] * m
		matrix.insert(0, listColumn)
		for i in range(n + 1):
			matrix[i].insert(0, 0)
		for i in range(n + 1):
			prev = 0
			for j in range(m + 1):
				matrix[i][j] += prev
				prev = matrix[i][j]
		for i in range(m + 1):
			prev = 0
			for j in range(n + 1):
				matrix[j][i] += prev
				prev = matrix[j][i]
		print(func(matrix, n, m, k))
except:
	pass


try:

	def fun(l, N, M, K, order):
		count = 0
		a = min(M, N)
		while order < a + 1:
			i = order
			j = M
			while i < N + 1:
				x = i - order + 1
				y = j - order + 1
				z = l[i][j] - l[x - 1][j] - l[i][y - 1] + l[x - 1][y - 1]
				if z / (order * order) < K:
					i += 1
				else:
					start = order
					end = M
					while start <= end:
						mid = (start + end) // 2
						x = i - order + 1
						y = mid - order + 1
						z = l[i][mid] - l[x - 1][mid] - l[i][y - 1] + l[x - 1][y - 1]
						if z / (order * order) < K:
							start = mid + 1
						else:
							ans = mid
							end = mid - 1
					count += M - ans + 1
					i += 1
			order += 1
		return count
	T = int(input())
	for i in range(T):
		(N, M, K) = map(int, input().split())
		l = []
		for i in range(N):
			a = list(map(int, input().split()))
			l.append(a)
		for i in range(N):
			sum = 0
			for j in range(M):
				sum += l[i][j]
				l[i][j] = sum
		for i in range(M):
			sum = 0
			for j in range(N):
				sum += l[j][i]
				l[j][i] = sum
		p = M * [0]
		l.insert(0, p)
		for i in l:
			i.insert(0, 0)
		A = fun(l, N, M, K, 1)
		print(A)
except:
	pass


def getAnswer(n, m, k, mat):
	if k > mat[n - 1][m - 1]:
		return 0
	count = 0
	dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
	for k1 in range(1, min(m, n) + 1):
		for i in range(1, n + 1 - k1 + 1):
			li = 1
			ri = m - k1 + 1
			md = (li + ri) // 2
			fg = False
			si = 0
			while li <= ri:
				md = (li + ri) // 2
				s1 = dp[i + k1 - 1][md + k1 - 1] - dp[i - 1][md + k1 - 1] - dp[i + k1 - 1][md - 1] + dp[i - 1][md - 1]
				if s1 / (k1 * k1) >= k:
					fg = True
					si = md
					ri = md - 1
				else:
					li = md + 1
			if fg == True:
				count = count + m - k1 + 1 - si + 1
	return count
t = int(input())
for i in range(t):
	d = list(map(int, input().split(' ')))
	mat = []
	for i in range(d[0]):
		e = list(map(int, input().split(' ')))
		mat.append(e)
	ans = getAnswer(d[0], d[1], d[2], mat)
	print(ans)


def bsearch(aux, k, m, size, i):
	lo = size
	hi = m
	ans = 0
	while lo <= hi:
		mid = (lo + hi) // 2
		x = i - size + 1
		y = mid - size + 1
		subsum = aux[i][mid] - aux[x - 1][mid] - aux[i][y - 1] + aux[x - 1][y - 1]
		avg = subsum / size ** 2
		if avg < k:
			lo = mid + 1
		else:
			ans = mid
			hi = mid - 1
	return ans

def count(aux, n, m, k):
	ans = 0
	for size in range(1, n + 1):
		i = size
		j = m
		while i < n + 1:
			x = i - size + 1
			y = j - size + 1
			subsum = aux[i][j] - aux[x - 1][j] - aux[i][y - 1] + aux[x - 1][y - 1]
			avg = subsum / size ** 2
			if avg < k:
				i += 1
			else:
				f = bsearch(aux, k, m, size, i)
				ans += m - f + 1
				i += 1
	return ans
t = int(input())
for _ in range(t):
	(n, m, k) = [int(k) for k in input().split()]
	mat = []
	aux = [[0] * (m + 1)]
	for j in range(n):
		mat.append([int(c) for c in input().split()])
		aux.append([0 for x in range(m + 1)])
	ans = 0
	for l in range(0, n):
		s = 0
		for b in range(0, m):
			s += mat[l][b]
			mat[l][b] = s
			aux[l + 1][b + 1] = mat[l][b]
	for l in range(0, m):
		s = 0
		for b in range(0, n):
			s += mat[b][l]
			mat[b][l] = s
			aux[b + 1][l + 1] = mat[b][l]
	ans = count(aux, n, m, k)
	print(ans)


def summer(a, b, x, y, l, pre):
	(prev, ptr) = pre
	if y > 0:
		t = c[x][y + l - 1] - c[x][y - 1]
	else:
		t = c[x][y + l - 1]
	if y == ptr:
		return prev + t + b[x + l - 1][y + l - 1] - b[x][y + l - 1]
	else:
		return prev + t + b[x + l - 1][y] - b[x][y]
for _ in range(int(input())):
	(a, b, c) = ([], [], [])
	(n, m, k) = list(map(int, input().split()))
	for i in range(n):
		x = list(map(int, input().split()))
		a.append(x)
	if a[0][0] >= k:
		s = 0
		for i in range(min(n, m)):
			s += (n - i) * (m - i)
		print(s)
		continue
	if a[-1][-1] < k:
		print(0)
		continue
	b.append(a[0])
	y = [a[0][0]]
	for j in range(1, m):
		y.append(y[j - 1] + a[0][j])
	c.append(y)
	for i in range(1, n):
		(x, y) = ([], [])
		for j in range(m):
			if j:
				y.append(y[j - 1] + a[i][j])
			else:
				y.append(a[i][j])
			x.append(a[i][j] + b[i - 1][j])
		b.append(x)
		c.append(y)
	(start, count, max_l) = (0, 0, min(n, m))
	for i in range(m):
		if a[n - 1][i] >= k:
			start = i
			break
	(i, j) = (n - 1, start)
	while i >= 0 and j < m:
		if a[i][j] >= k:
			count += m - j
			i -= 1
		else:
			j += 1
	prev = [a[n - 1][start], start]
	for l in range(2, max_l + 1):
		(i, j) = (n - l, start - l + 1)
		if j < 0:
			j = 0
		s = summer(a, b, i, j, l, prev)
		prev = [s, j]
		target = k * l ** 2
		while i >= 0 and j <= m - l:
			temp = 0
			if s >= target:
				count += m - l - j + 1
				i -= 1
				if i < 0:
					break
				if j > 0:
					t1 = c[i][j + l - 1] - c[i][j - 1]
					t2 = c[i + l][j + l - 1] - c[i + l][j - 1]
					s += t1 - t2
				else:
					s += c[i][j + l - 1] - c[i + l][j + l - 1]
			else:
				j += 1
				if j > m - l:
					break
				if i > 0:
					t1 = b[i + l - 1][j + l - 1] - b[i - 1][j + l - 1]
					t2 = b[i + l - 1][j - 1] - b[i - 1][j - 1]
					s += t1 - t2
				else:
					s += b[i + l - 1][j + l - 1] - b[i + l - 1][j - 1]
	print(count)


def binarysearch(res, l, i, j):
	lo = 1
	hi = l
	while lo < hi:
		mid = lo + (hi - lo + 1) // 2
		if res[i][j] - res[i - mid][j] - res[i][j - mid] + res[i - mid][j - mid] >= 0:
			lo = mid
		else:
			hi = mid - 1
	if res[i][j] - res[i - lo][j] - res[i][j - lo] + res[i - lo][j - lo] >= 0:
		return lo
	return 0
t = int(input())
while t:
	t -= 1
	(n, m, k) = list(map(int, input().split()))
	res = [[0 for i in range(m + 1)] for j in range(n + 1)]
	for i in range(n):
		temp = list(map(int, input().split()))
		for j in range(m):
			res[i + 1][j + 1] = temp[j] - k + res[i][j + 1] + res[i + 1][j] - res[i][j]
	ans = 0
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			l = min(i, j)
			ans += binarysearch(res, l, i, j)
	print(ans)


t = int(input())
for _ in range(t):
	ans = 0
	(n, m, k) = map(int, input().split(' '))
	a = []
	for i in range(n):
		a.append(list(map(int, input().split(' '))))
	b = [[0 for j in range(m + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			b[i][j] = a[i - 1][j - 1] + (b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1])
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			x1 = min(n - i, m - j)
			if a[i - 1][j - 1] >= k:
				if n - i >= m - j:
					ans += (x1 + 1) * (x1 + 2) // 2
					break
				else:
					ans += (x1 + 1) * (x1 + 2) // 2 + (m - j - n + i) * (n - i + 1)
					break
			else:
				tans = 0
				tp = 0
				tr = 2 * x1
				if tp != tr:
					while tp + 1 != tr and tp < x1:
						tq = (tp + tr) // 2
						if k * (tq + 1) * (tq + 1) <= b[i + tq][j + tq] - b[i + tq][j - 1] - b[i - 1][j + tq] + b[i - 1][j - 1]:
							tr = tq
						else:
							tp = tq
					if tp < x1:
						tans = x1 - tr + 1
					else:
						tans = 0
				else:
					tans = 0
				ans += tans
	print(ans)