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

Doraemon has a matrix with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$). Let's denote the element in row $i$ and column $j$ by $A_{i,j}$. Next, let's define a sub-row of a row $r$ as a sequence $A_{r, x}, A_{r, x+1}, \ldots, A_{r, y}$ for some $x$ and $y$ ($1 ≤ x ≤ y ≤ M$) and a sub-column of a column $c$ by $A_{x, c}, A_{x+1, c}, \ldots, A_{y, c}$ for some $x$ and $y$ ($1 ≤ x ≤ y ≤ N$).

You need to find the number of pairs (sub-row of some row, sub-column of some column) with the following properties:
1. Both sequences (the sub-row and the sub-column) have the same length.
2. This length is odd.
3. The central elements of both sequences are the same (they correspond to the same element of the matrix).
4. Both sequences are palindromes.

------  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 two space-separated integers $N$ and $M$. 
$N$ lines follow. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of these lines contains $M$ space-separated integers $A_{i, 1}, A_{i, 2}, \ldots, A_{i, M}$.

------  Output ------
For each test case, print a single line containing one integer ― the number of valid pairs.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N, M$
$N \cdot M ≤ 10^{5}$
$1 ≤ A_{i, j} ≤ 10^{6}$ for each valid $i, j$
the sum of $N \cdot M$ over all test cases does not exceed $3 \cdot 10^{5}$

------  Subtasks ------
Subtask #1 (30 points):
$T ≤ 10$
$N \cdot M ≤ 10^{3}$  

Subtask #2 (70 points): original constraints

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

3 3

2 1 2

1 1 1

2 1 2
----- Sample Output 1 ------ 
10
----- explanation 1 ------ 
Example case 1: Each element forms a valid pair (where the sub-row and sub-column contain only this element) and the middle row and middle column also form one valid pair.

Difficulty: MEDIUM_HARD
Tags: Data structures

Implementation

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
def func(a, n, m, final):
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			k = 1
			while i - k >= 0 and i + k < n and (j - k >= 0) and (j + k < m):
				if a[i - k][j] == a[i + k][j] and a[i][j - k] == a[i][j + k]:
					final += 1
				else:
					break
				k += 1
	return final
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		l = list(map(int, input().split()))
		arr.append(l)
	print(func(arr, n, m, n * m))


def solve(mat, row, col, count):
	for i in range(row):
		for j in range(col):
			maxRange = min(i, row - i - 1, j, col - j - 1)
			for k in range(1, maxRange + 1):
				if mat[i][j - k] == mat[i][j + k] and mat[i - k][j] == mat[i + k][j]:
					count += 1
				else:
					break
	return count
for _ in range(int(input())):
	(r, c) = map(int, input().split())
	arr = []
	for i in range(r):
		a = list(map(str, input().split()))
		arr.append(a)
	print(solve(arr, r, c, r * c))


def snek(s, j, k):
	x = 1
	c = 0
	while j - x >= 0 and j + x < n and (k - x >= 0) and (k + x < m):
		if s[j - x][k] == s[j + x][k] and s[j][k - x] == s[j][k + x]:
			c += 1
			x += 1
		else:
			break
	return c
t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	s = []
	ans = 0
	for i in range(n):
		s.append(list(map(int, input().split())))
	for j in range(1, n):
		for k in range(1, m):
			ans += snek(s, j, k)
	print(n * m + ans)


def countt(mat, i, j):
	x = 1
	count = 0
	while i - x >= 0 and i + x < n and (j - x >= 0) and (j + x < m):
		if mat[i - x][j] == mat[i + x][j] and mat[i][j - x] == mat[i][j + x]:
			count += 1
			x += 1
		else:
			break
	return count
t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	mat = []
	sum = 0
	for i in range(n):
		mat.append(list(map(int, input().split())))
	for i in range(1, n):
		for j in range(1, m):
			sum += countt(mat, i, j)
	print(n * m + sum)


def matrix(a, i, j):
	x = 1
	ans = 0
	while j - x >= 0 and i - x >= 0 and (j + x < m) and (i + x < n):
		if a[i][j - x] == a[i][j + x] and a[i - x][j] == a[i + x][j]:
			x += 1
			ans += 1
		else:
			break
	return ans
for _ in range(0, int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	sum = 0
	for i in range(1, n):
		for j in range(1, m):
			sum += matrix(a, i, j)
	print(sum + n * m)


def solve(matrix, n, m):
	count = 0
	for i in range(n):
		for j in range(m):
			maxLength = min(i, n - i - 1, j, m - j - 1)
			for k in range(1, maxLength + 1):
				if matrix[i][j - k] == matrix[i][j + k] and matrix[i - k][j] == matrix[i + k][j]:
					count += 1
				else:
					break
	return count + n * m
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	matrix = []
	for i in range(n):
		entries = list(map(int, input().split()))
		matrix.append(entries[:])
	print(solve(matrix, n, m))


def check(mat, i, j, count):
	k = 1
	while i - k >= 0 and i + k < r and (j - k >= 0) and (j + k < c):
		if mat[i - k][j] == mat[i + k][j] and mat[i][j - k] == mat[i][j + k]:
			count += 1
			k += 1
		else:
			break
	return count
t = int(input())
for z in range(t):
	(r, c) = map(int, input().split())
	mat = []
	count = 0
	for i in range(r):
		row = list(map(int, input().split()))
		mat += [row]
	for i in range(1, r):
		for j in range(1, c):
			count = check(mat, i, j, count)
	print(r * c + count)


def Shwetank(l, t):
	count = 0
	for i in range(1, n - 1):
		a = l[i]
		for j in range(1, m - 1):
			b = t[j]
			r1 = j - 1
			r2 = j + 1
			c1 = i - 1
			c2 = i + 1
			while r1 >= 0 and r2 <= m - 1 and (c1 >= 0) and (c2 <= n - 1):
				if a[r1] == a[r2] and b[c1] == b[c2]:
					count += 1
					r1 -= 1
					r2 += 1
					c1 -= 1
					c2 += 1
				else:
					break
	return count
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	count = 0
	for i in range(n):
		l.append(list(map(int, input().split())))
	t = [[l[j][i] for j in range(len(l))] for i in range(len(l[0]))]
	count += Shwetank(l, t)
	count += n * m
	print(count)


def doremon(grid):
	n = len(grid)
	m = len(grid[0])
	summ = 0
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			for k in range(1, min(i, j, m - j - 1, n - i - 1) + 1):
				if grid[i + k][j] == grid[i - k][j] and grid[i][j + k] == grid[i][j - k]:
					summ = summ + 1
				else:
					break
	result = summ + n * m
	return result
t = int(input())
for i in range(0, t):
	nm = list(map(int, input().strip().split()))
	n = nm[0]
	m = nm[1]
	arr = []
	for j in range(0, n):
		scratch = list(map(int, input().strip().split()))
		arr.append(scratch)
	print(doremon(arr))


test = False

def calc(grid, r, c):
	maxRange = min(r + 1, c + 1, M - c, N - r)
	k = 1
	temp = 0
	while k < maxRange:
		if grid[r - k][c] == grid[r + k][c] and grid[r][c - k] == grid[r][c + k]:
			temp += 1
		else:
			return temp
		k += 1
	return temp
T = int(input().strip())
for i in range(T):
	(N, M) = map(int, input().strip().split(' '))
	grid = []
	for j in range(N):
		grid.append([int(x) for x in input().strip().split(' ')])
	if test:
		print(N, M, grid)
	answer = 0
	for r in range(1, N - 1):
		for c in range(1, M - 1):
			answer += calc(grid, r, c)
	answer += M * N
	print(answer)


def solve(t, i, j):
	count = 0
	mini1 = min(i, n - 1 - i)
	mini2 = min(j, m - 1 - j)
	z = min(mini1, mini2) + 1
	q = 1
	while q < z:
		if t[i][j - q] == t[i][j + q] and t[i - q][j] == t[i + q][j]:
			count += 1
			q += 1
		else:
			break
	return count
for i in range(int(input())):
	z = list(map(int, input().split()))
	n = z[0]
	m = z[-1]
	t = []
	for i in range(n):
		t.append([int(i) for i in input().split()])
	count = n * m
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			o = solve(t, i, j)
			count += o
	print(count)


t = int(input())
for test in range(t):
	matrix = []
	(n, m) = map(int, input().split())
	trans_matrix = [[0 for x in range(n)] for y in range(m)]
	for k in range(n):
		rows = list(map(int, input().split()))
		matrix.append(rows)
	for i in range(m):
		for j in range(n):
			trans_matrix[i][j] = matrix[j][i]
	if m >= 3 and n >= 3:
		count = 0
		for i in range(1, n - 1):
			j = 1
			while j < int(m // 2):
				c = 1
				cnt = 0
				if i > int(n // 2):
					min_val = min(2 * (j + 1) - 1, 2 * (n - i) - 1)
				else:
					i = i
					min_val = min(2 * (j + 1) - 1, 2 * (i + 1) - 1)
				itr = (min_val - 1) // 2
				e = matrix[i][j - itr:j + itr + 1]
				e.reverse()
				e_rev = e
				d = trans_matrix[j][i - itr:i + itr + 1]
				d.reverse()
				d_rev = d
				if j - itr >= 0 and j + itr < m and (i - itr >= 0) and (i + itr < n) and (e_rev == matrix[i][j - itr:j + itr + 1]) and (d_rev == trans_matrix[j][i - itr:i + itr + 1]):
					count += itr
				else:
					while c <= itr:
						if j - c >= 0 and j + c < m and (i - c >= 0) and (i + c < n) and (matrix[i][j - c] == matrix[i][j + c]) and (matrix[i - c][j] == matrix[i + c][j]):
							c += 1
							cnt += 1
						else:
							break
					count += cnt
				j += 1
			j = int(m // 2)
			while j < m - 1:
				cnt = 0
				c = 1
				less = m - j
				if i > int(n // 2):
					min_val = min(2 * less - 1, 2 * (n - i) - 1)
				else:
					i = i
					min_val = min(2 * less - 1, 2 * (i + 1) - 1)
				itr = (min_val - 1) // 2
				e = matrix[i][j - itr:j + itr + 1]
				e.reverse()
				e_rev = e
				d = trans_matrix[j][i - itr:i + itr + 1]
				d.reverse()
				d_rev = d
				if j - itr >= 0 and j + itr < m and (i - itr >= 0) and (i + itr < n) and (e_rev == matrix[i][j - itr:j + itr + 1]) and (d_rev == trans_matrix[j][i - itr:i + itr + 1]):
					count += itr
				else:
					while c <= itr:
						if j - c >= 0 and j + c < m and (i - c >= 0) and (i + c < n) and (matrix[i][j - c] == matrix[i][j + c]) and (matrix[i - c][j] == matrix[i + c][j]):
							c += 1
							cnt += 1
						else:
							break
					count += cnt
				j += 1
		ans = count + m * n
	else:
		ans = m * n
	print(ans)


def palindrome(mat, i, j, c):
	h = 0
	for k in range(1, c + 1):
		if mat[i][j - k] == mat[i][j + k]:
			if mat[i - k][j] == mat[i + k][j]:
				h = h + 1
			else:
				break
		else:
			break
	return h
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	mat = []
	for i in range(n):
		a = list(map(int, input().split()))
		mat.append(a)
	k = 0
	for i in range(n):
		for j in range(m):
			if i > 0 and j > 0:
				if n - 1 - i > 0 and m - 1 - j > 0:
					a = min(i, n - 1 - i)
					b = min(j, m - 1 - j)
					c = min(a, b)
					k = k + palindrome(mat, i, j, c)
	print(k + n * m)


def largest_palind(matrix, i, j, n, m):
	limit = min(min(i, abs(n - 1 - i)), min(j, abs(m - 1 - j)))
	max_i = 0
	max_j = 0
	for k in range(1, limit + 1):
		if matrix[i + k][j] == matrix[i - k][j]:
			max_i = k
		else:
			break
		if matrix[i][j + k] == matrix[i][j - k]:
			max_j = k
		else:
			break
	return min(max_i, max_j)
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	matrix = []
	sum = n * m
	for i in range(n):
		row = [int(x) for x in input().split()]
		matrix.append(row)
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			val = largest_palind(matrix, i, j, n, m)
			sum += val
	print(sum)


def func(arr, n, m):
	ans = n * m
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			k = 1
			while i - k >= 0 and i + k < n and (j - k >= 0) and (j + k < m):
				if arr[i - k][j] == arr[i + k][j] and arr[i][j - k] == arr[i][j + k]:
					ans += 1
				else:
					break
				k += 1
	return ans
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
	result = func(arr, n, m)
	print(result)


def func(n, m, matrix):
	s = n * m
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			if matrix[i][j - 1] == matrix[i][j + 1] and matrix[i - 1][j] == matrix[i + 1][j]:
				s += 1
				k = 2
				while j + k < m and i + k < n and (i - k >= 0) and (j - k >= 0) and (matrix[i][j - k] == matrix[i][j + k]) and (matrix[i - k][j] == matrix[i + k][j]):
					s += 1
					k += 1
	print(s)
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	matrix = []
	for i in range(n):
		a = input().split()
		matrix.append(a)
	func(n, m, matrix)


import sys

def func(a, i, j):
	d = 1
	z = a[i]
	temp = 0
	while True:
		if i - d >= 0 and i + d < n and (j - d >= 0) and (j + d < m):
			if z[j - d] != z[j + d] or a[i - d][j] != a[i + d][j]:
				return temp
			else:
				temp += 1
				d += 1
		else:
			return temp
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list()
	for i in range(n):
		a.append(list(map(int, input().split())))
	ans = n * m
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			o = func(a, i, j)
			ans += o
	print(ans)


def fun(a, i, j):
	x = 1
	c = 0
	while i - x >= 0 and i + x < n and (j - x >= 0) and (j + x < m):
		if a[i - x][j] == a[i + x][j] and a[i][j - x] == a[i][j + x]:
			x += 1
			c += 1
		else:
			break
	return c
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	a = []
	ans = 0
	for i in range(n):
		a.append(list(map(int, input().split())))
	for i in range(1, n):
		for j in range(1, m):
			ans += fun(a, i, j)
	print(n * m + ans)


def func(li, i, j, n, m):
	a = 1
	count = 0
	while (i - a >= 0 and i + a < n) and (j - a >= 0 and j + a < m):
		if li[i][j - a] == li[i][j + a] and li[i - a][j] == li[i + a][j]:
			count += 1
			a += 1
		else:
			break
	return count
for k in range(int(input(''))):
	li = []
	count = 0
	(n, m) = map(int, input('').split(' '))
	for j in range(n):
		li.append(list(map(int, input('').split(' '))))
	for i in range(1, n):
		for j in range(1, m):
			count += func(li, i, j, n, m)
	ans = n * m + count
	print(ans)


def is_palindrome(i, j, mat, m, n):
	count = 0
	t = 0
	while True:
		try:
			if (i - t < 0 or j - t < 0) or i + t > m or j + t > n:
				return count
			if mat[i - t][j] == mat[i + t][j] and mat[i][j - t] == mat[i][j + t]:
				count += 1
				t += 1
			else:
				return count
		except:
			return count
t = int(input())
for _ in range(t):
	(M, N) = map(int, input().split())
	mat = []
	for i in range(M):
		mat.append(input().split())
	count = 0
	i = 0
	while i < M:
		j = 0
		while j < N:
			count += is_palindrome(i, j, mat, M - 1, N - 1)
			j += 1
		i += 1
	print(count)


def fun(arr, i, j, n, m):
	lans = 0
	l = 1
	while i - l >= 0 and i + l < n and (j - l >= 0) and (j + l < m):
		if arr[i + l][j] == arr[i - l][j] and arr[i][j - l] == arr[i][j + l]:
			lans += 1
			l += 1
		else:
			break
	return lans
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append([int(x) for x in input().split()])
	ans = n * m
	for i in range(n):
		for j in range(m):
			ans += fun(arr, i, j, n, m)
	print(ans)


def fun(i, j):
	x = 1
	ans = 0
	while i - x >= 0 and i + x < n and (j - x >= 0) and (j + x < m):
		if matrix[i - x][j] == matrix[i + x][j] and matrix[i][j - x] == matrix[i][j + x]:
			ans += 1
			x += 1
		else:
			break
	return ans
try:
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		matrix = []
		total = n * m
		for i in range(n):
			temp = [int(x) for x in input().split()][:m]
			matrix.append(temp)
		for i in range(1, n):
			for j in range(1, m):
				total += fun(i, j)
		print(total)
except Exception as e:
	print(e)


def doremon(c, i, j):
	u = v = i
	z = c[i]
	w = x = j
	crt = 0
	while u >= 0 and v < a and (w >= 0) and (x < b) and (c[u][j] == c[v][j]) and (c[i][w] == c[i][x]):
		u = u - 1
		v = v + 1
		w = w - 1
		x = x + 1
		crt += 1
	return crt
import sys
n = int(input())
while n != 0:
	(a, b) = map(int, input().split())
	c = list()
	crt = 0
	for i in range(a):
		c.append(list(map(int, sys.stdin.readline().split())))
	for i in range(a):
		for j in range(b):
			t = doremon(c, i, j)
			crt = crt + t
	print(crt)
	n = n - 1


def fen(l1, k, l):
	z = l1[k]
	e = 1
	ce = 0
	while 1:
		if l - e >= 0 and l + e < q and (k - e >= 0) and (k + e < p):
			if l1[k - e][l] != l1[k + e][l] or z[l - e] != z[l + e]:
				return ce
			ce = ce + 1
			e = e + 1
		else:
			break
	return ce
import sys
T = int(input())
for i in range(T):
	l1 = list()
	ce = 0
	(p, q) = list(map(int, input().split()))
	ce = p * q
	for j in range(p):
		l1.append(list(map(int, sys.stdin.readline().split())))
	for k in range(1, p - 1):
		for l in range(1, q - 1):
			o = fen(l1, k, l)
			ce = ce + o
	print(ce)


def calcPairs(A, i, j, xR, M, N):
	p = 0
	for x in range(1, xR):
		if j + x < M and j - x >= 0 and (i + x < N) and (i - x >= 0):
			if A[i][j - x] == A[i][j + x] and A[i + x][j] == A[i - x][j]:
				p += 1
				continue
			break
		break
	return p
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	A = []
	for i in range(N):
		A.append(list(map(int, input().split())))
	pairs = N * M
	if N < 3 or M < 3:
		print(pairs)
	else:
		xR = min(N - 1, M - 1)
		for i in range(1, N - 1):
			for j in range(1, M - 1):
				pairs += calcPairs(A, i, j, xR, M, N)
		print(pairs)


def fun(mat, i, j, n, m):
	x = 1
	c = 0
	while i - x >= 0 and i + x < n and (j - x >= 0) and (j + x < m):
		if mat[i - x][j] == mat[i + x][j] and mat[i][j - x] == mat[i][j + x]:
			c += 1
			x += 1
		else:
			break
	return c
import sys
for _ in range(int(input())):
	l = list(map(int, input().split()))
	(n, m) = (l[0], l[1])
	mat = []
	for i in range(n):
		mat.append(list(map(int, input().split())))
	total = 0
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			total += fun(mat, i, j, n, m)
	print(total + n * m)


def fun(a, i, j):
	p = 1
	asi = 0
	while 1:
		if i - p >= 0 and i + p < n and (j - p >= 0) and (j + p < m):
			if a[i - p][j] == a[i + p][j] and a[i][j - p] == a[i][j + p]:
				asi = asi + 1
				p = p + 1
			else:
				break
		else:
			break
	return asi
from sys import stdin
t = int(input())
for k in range(t):
	(n, m) = map(int, input().strip().split())
	a = []
	for j in range(n):
		a.append(list(map(int, stdin.readline().strip().split())))
	ansi = n * m
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			asi = fun(a, i, j)
			ansi = ansi + asi
	print(ansi)


from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())
mod = int(1000000000.0) + 7

def solve(mat, n, m):
	ans = m * n
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			temp = 1
			while i + temp < n and j + temp < m and (j - temp >= 0) and (i - temp >= 0):
				if mat[i][j + temp] == mat[i][j - temp] and mat[i + temp][j] == mat[i - temp][j]:
					temp += 1
					ans += 1
				else:
					break
	return ans
for _ in range(iinput()):
	(n, m) = rinput()
	mat = [[0 for j in range(m)] for i in range(n)]
	for i in range(n):
		temp = rlinput()
		for j in range(m):
			mat[i][j] = temp[j]
	print(solve(mat, n, m))


def f(n, m, i, j, l):
	k = min(i, n - i - 1, j, m - j - 1)
	v = 1
	ans = 0
	while v != k + 1:
		if l[i - v][j] == l[i + v][j] and l[i][j - v] == l[i][j + v]:
			ans = ans + 1
		else:
			break
		v = v + 1
	return ans
t = int(input())
for x in range(t):
	(n, m) = map(int, input().split())
	l = [[]] * n
	fans = m * n
	for y in range(n):
		l[y] = list(map(int, input().split()))
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			fans = fans + f(n, m, i, j, l)
	print(fans)


def getPairs(i, j, M, N, mat):
	minSteps = min(i - 0, M - i - 1, j - 0, N - j - 1)
	count = 0
	for x in range(1, minSteps + 1):
		if mat[i - x][j] == mat[i + x][j] and mat[i][j - x] == mat[i][j + x]:
			count += 1
		else:
			break
	return count
T = int(input())
for t in range(T):
	(M, N) = map(int, list(input().strip().split()))
	matrix = list()
	for mat in range(M):
		matrix.append(list(map(int, input().strip().split())))
	count = M * N
	for i in range(1, M - 1):
		for j in range(1, N - 1):
			count = count + getPairs(i, j, M, N, matrix)
	print(count)


def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		ctr = 0
		l2 = []
		for i in range(n):
			a = list(map(int, input().split()))
			l2.append(a)
		for i in range(n):
			for j in range(m):
				l3 = 1
				while l3 <= i and l3 <= j and (l3 + i < n) and (l3 + j < m) and (l2[i - l3][j] == l2[i + l3][j]) and (l2[i][j - l3] == l2[i][j + l3]):
					l3 += 1
				ctr += l3
		print(ctr)
main()


def main():
	from sys import stdin, stdout
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		ctr = 0
		l2 = []
		for i in range(n):
			a = list(map(int, input().split()))
			l2.append(a)
		for i in range(0, n):
			for j in range(0, m):
				l3 = 1
				while l3 <= i and l3 <= j and (l3 + i < n) and (l3 + j < m) and (l2[i - l3][j] == l2[i + l3][j]) and (l2[i][j - l3] == l2[i][j + l3]):
					l3 += 1
				ctr += l3
		print(ctr)
main()


def main():
	from sys import stdin, stdout
	t = int(input())
	for i in range(0, t):
		(n, m) = map(int, input().split())
		a = []
		for i in range(n):
			b = list(map(int, input().split()))
			a.append(b)
			c = 0
		for i in range(0, n):
			for j in range(0, m):
				k = 1
				while i - k >= 0 and j - k >= 0 and (i + k < n) and (j + k < m) and (a[i - k][j] == a[i + k][j]) and (a[i][j - k] == a[i][j + k]):
					k = k + 1
				c = c + k
		print(c)
main()


def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		a = [0] * n
		for i in range(n):
			a[i] = list(map(int, input().split()))
		ans = 0
		for i in range(n):
			if i == 0 or i == n - 1:
				ans += m
			else:
				for j in range(m):
					if j == 0 or j == m - 1:
						ans += 1
					else:
						(l, r, u, d) = (j, j, i, i)
						ans += 1
						l -= 1
						r += 1
						u -= 1
						d += 1
						while l >= 0 and r < m and (u >= 0) and (d < n):
							if a[i][l] == a[i][r] and a[u][j] == a[d][j]:
								ans += 1
								l -= 1
								r += 1
								u -= 1
								d += 1
							else:
								break
		print(ans)
main()


def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		a = []
		for x in range(n):
			a.append(list(map(int, input().split())))
		c = 0
		for i in range(0, n):
			for j in range(0, m):
				k = 1
				while i - k >= 0 and j - k >= 0 and (i + k < n) and (j + k < m) and (a[i - k][j] == a[i + k][j]) and (a[i][j - k] == a[i][j + k]):
					k += 1
				c += k
		print(c)
main()


def check(i, j, l1, n, m):
	l = min(i, j, m - j, n - i)
	s = 0
	for k in range(1, l + 1):
		if l1[i + k][j] == l1[i - k][j] and l1[i][j + k] == l1[i][j - k]:
			s = s + 1
		else:
			break
	return s
for a in range(int(input())):
	(n, m) = map(int, input().split())
	l1 = []
	sum1 = m * n
	for i in range(n):
		l1.append(list(map(int, input().split())))
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			sum1 = sum1 + check(i, j, l1, n - 1, m - 1)
	print(sum1)


II = lambda : [int(x) for x in input().split()]
I2 = lambda : int(input())
T = int(input())
for _ in range(T):
	a = II()
	(N, M) = a
	A = [II() for _ in range(N)]
	H = [[1] * M for _ in range(N)]
	for i in range(N):
		(c, r) = (0, 0)
		for j in range(1, M - 1):
			m_pos = c - (j - c)
			m_val = H[i][m_pos] if m_pos >= 0 else 1
			if j + m_val - 1 < r:
				H[i][j] = m_val
				continue
			m_val = max(min(r - j + 1, m_val), 1)
			H[i][j] = m_val
			for d in range(m_val, M):
				if 0 <= j - d <= j + d < M and A[i][j - d] == A[i][j + d]:
					H[i][j] += 1
				else:
					(c, r) = (j, j + d - 1)
					break
	V = [[1] * M for _ in range(N)]
	for j in range(M):
		(c, r) = (0, 0)
		for i in range(1, N - 1):
			m_pos = c - (i - c)
			m_val = V[m_pos][j] if m_pos >= 0 else 1
			if i + m_val - 1 < r:
				V[i][j] = m_val
				continue
			m_val = max(min(r - i + 1, m_val), 1)
			V[i][j] = m_val
			for d in range(m_val, M):
				if 0 <= i - d <= i + d < N and A[i - d][j] == A[i + d][j]:
					V[i][j] += 1
				else:
					(c, r) = (i, i + d - 1)
					break
	count = 0
	for i in range(N):
		for j in range(M):
			count += min(H[i][j], V[i][j])
	print(count)


test = int(input())
for t in range(test):
	matrix = []
	(n, m) = map(int, input().split())
	transpose_matrix = [[0 for x in range(n)] for y in range(m)]
	for a in range(n):
		rows = list(map(int, input().split()))
		matrix.append(rows)
	for i in range(m):
		for j in range(n):
			transpose_matrix[i][j] = matrix[j][i]
	if m >= 3 and n >= 3:
		count1 = 0
		for i in range(1, n - 1):
			j = 1
			while j < int(m // 2):
				count = 0
				if i > int(n // 2):
					max_val = min(2 * (j + 1) - 1, 2 * (n - i) - 1)
				else:
					i = i
					max_val = min(2 * (j + 1) - 1, 2 * (i + 1) - 1)
				itr = (max_val - 1) // 2
				sub_row = matrix[i][j - itr:j + itr + 1]
				sub_row.reverse()
				sub_row_rev = sub_row
				sub_col = transpose_matrix[j][i - itr:i + itr + 1]
				sub_col.reverse()
				sub_col_rev = sub_col
				k = 1
				if j - itr >= 0 and j + itr < m and (i - itr >= 0) and (i + itr < n) and (sub_row_rev == matrix[i][j - itr:j + itr + 1] and sub_col_rev == transpose_matrix[j][i - itr:i + itr + 1]):
					count1 += itr
				else:
					while k <= itr:
						if j - k >= 0 and j + k < m and (i - k >= 0) and (i + k < n) and (matrix[i][j - k] == matrix[i][j + k] and matrix[i - k][j] == matrix[i + k][j]):
							k += 1
							count += 1
						else:
							break
					count1 += count
				j += 1
			j = int(m // 2)
			while j < m - 1:
				count = 0
				rev = m - j
				if i > int(n // 2):
					max_val = min(2 * rev - 1, 2 * (n - i) - 1)
				else:
					i = i
					max_val = min(2 * rev - 1, 2 * (i + 1) - 1)
				itr = (max_val - 1) // 2
				sub_row = matrix[i][j - itr:j + itr + 1]
				sub_row.reverse()
				sub_row_rev = sub_row
				sub_col = transpose_matrix[j][i - itr:i + itr + 1]
				sub_col.reverse()
				sub_col_rev = sub_col
				k = 1
				if j - itr >= 0 and j + itr < m and (i - itr >= 0) and (i + itr < n) and (sub_row_rev == matrix[i][j - itr:j + itr + 1] and sub_col_rev == transpose_matrix[j][i - itr:i + itr + 1]):
					count1 += itr
				else:
					while k <= itr:
						if j - k >= 0 and j + k < m and (i - k >= 0) and (i + k < n) and (matrix[i][j - k] == matrix[i][j + k] and matrix[i - k][j] == matrix[i + k][j]):
							k += 1
							count += 1
						else:
							break
					count1 += count
				j += 1
		answer = count1 + m * n
	else:
		answer = m * n
	print(answer)


def check(a, b, m, A, B):
	x = min(a, b, A - a, B - b)
	s = 0
	f1 = 0
	for j in range(1, x + 1):
		if m[a - j][b] == m[a + j][b] and m[a][b - j] == m[a][b + j]:
			s = s + 1
		else:
			f1 = 1
			break
	return s
t = int(input())
for i in range(0, t):
	(N, M) = map(int, input().split())
	arr = []
	for j in range(0, N):
		m = list(map(int, input().split()))
		arr.append(m)
	ans = N * M
	for p in range(1, N - 1):
		for q in range(1, M - 1):
			ans = ans + check(p, q, arr, N - 1, M - 1)
	print(ans)


def chfdora(A, n, m):
	c = 0
	for i in range(0, n):
		for j in range(0, m):
			d = min(i, n - 1 - i, j, m - j - 1)
			pnt = 0
			for k in range(0, d + 1):
				if A[i - k][j] != A[i + k][j]:
					break
				else:
					pnt += 1
			gnt = 0
			for k in range(0, d + 1):
				if A[i][j - k] != A[i][j + k]:
					break
				else:
					gnt += 1
			c += min(pnt, gnt)
	print(c)
T = int(input())
for i in range(0, T):
	(N, M) = map(int, input().split())
	A = []
	for i in range(N):
		B = list(map(int, input().split()))
		A.append(B)
	chfdora(A, N, M)


def dora(a, n, m):
	ans = 0
	for i in range(n):
		for j in range(m):
			d = min(i, n - 1 - i, j, m - 1 - j)
			p = 0
			for k in range(d + 1):
				if a[i - k][j] != a[i + k][j]:
					break
				else:
					p = p + 1
			g = 0
			for k in range(d + 1):
				if a[i][j - k] != a[i][j + k]:
					break
				else:
					g = g + 1
			ans = ans + min(p, g)
	print(ans)
for _ in range(int(input())):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	a = []
	for i in range(n):
		b = list(map(int, input().split()))
		a.append(b)
	dora(a, n, m)


def solve(l, n, m):
	cnt = n * m
	for r in range(1, n - 1):
		for c in range(1, m - 1):
			_min = min(min(c, m - c - 1), min(r, n - r - 1))
			for k in range(1, _min + 1):
				if l[r][c + k] == l[r][c - k] and l[r - k][c] == l[r + k][c]:
					cnt += 1
				else:
					break
	return cnt
t = int(input())
for _ in range(t):
	ans = 0
	(n, m) = map(int, input().split())
	l = []
	for rows in range(n):
		x = list(map(int, input().split()))
		l.append(x)
	ans += solve(l, n, m)
	print(ans)


def accumulator(A, ci, cj, limit):
	count = 0
	for k in range(1, limit + 1):
		if A[ci + k][cj] == A[ci - k][cj] and A[ci][cj + k] == A[ci][cj - k]:
			count += 1
		else:
			return count
	return count
tests = int(input())
for l in range(tests):
	(N, M) = input().split(' ')
	(N, M) = (int(N), int(M))
	A = []
	for ll in range(N):
		A.append([int(i) for i in input().split(' ')])
	count = N * M
	for i in range(1, N - 1):
		for j in range(1, M - 1):
			count += accumulator(A, i, j, min(i, j, N - i - 1, M - j - 1))
	print(count)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	dic = {}
	i = 0
	while i < n:
		j = 0
		o = []
		o = list(map(int, input().split()))
		while j < len(o):
			x = o[j]
			dic[i, j] = x
			j = j + 1
		i = i + 1
	som = 0
	k = 0
	d = {}
	while k < n:
		i = 0
		l = 0
		r = -1
		while i < m:
			if i > r:
				ld = i
				rd = i
				cnt = 0
				f = 0
				while f == 0:
					if dic[k, ld] == dic[k, rd]:
						ldd = ld - 1
						rdd = rd + 1
						cnt = cnt + 1
						if ldd >= 0 and rdd <= m - 1:
							ld = ldd
							rd = rdd
						else:
							f = 1
					else:
						ld = ld + 1
						rd = rd - 1
						f = 1
				d[k, i] = cnt
				if rd >= r:
					l = ld
					r = rd
			else:
				j = l + (r - i)
				if j - d[k, j] + 1 <= l:
					cnt = r - i + 1
					f = 0
					ld = i - cnt + 1
					rd = i + cnt - 1
					cnt = cnt - 1
					while f == 0:
						if dic[k, ld] == dic[k, rd]:
							ldd = ld - 1
							rdd = rd + 1
							cnt = cnt + 1
							if ldd >= 0 and rdd <= m - 1:
								ld = ldd
								rd = rdd
							else:
								f = 1
						else:
							ld = ld + 1
							rd = rd - 1
							f = 1
					d[k, i] = cnt
					if rd >= r:
						l = ld
						r = rd
				else:
					cnt = d[k, j]
					d[k, i] = cnt
					ld = i - cnt + 1
					rd = i + cnt - 1
					if rd >= r:
						l = ld
						r = rd
			i = i + 1
		k = k + 1
	k = 0
	do = {}
	while k < m:
		i = 0
		l = 0
		r = -1
		while i < n:
			if i > r:
				ld = i
				rd = i
				cnt = 0
				f = 0
				while f == 0:
					if dic[ld, k] == dic[rd, k]:
						ldd = ld - 1
						rdd = rd + 1
						cnt = cnt + 1
						if ldd >= 0 and rdd <= n - 1:
							ld = ldd
							rd = rdd
						else:
							f = 1
					else:
						ld = ld + 1
						rd = rd - 1
						f = 1
				do[i, k] = cnt
				q = d[i, k]
				mi = min(q, cnt)
				som = som + mi
				if rd >= r:
					l = ld
					r = rd
			else:
				j = l + (r - i)
				if j - do[j, k] + 1 <= l:
					cnt = r - i + 1
					f = 0
					ld = i - cnt + 1
					rd = i + cnt - 1
					cnt = cnt - 1
					while f == 0:
						if dic[ld, k] == dic[rd, k]:
							ldd = ld - 1
							rdd = rd + 1
							cnt = cnt + 1
							if ldd >= 0 and rdd <= n - 1:
								ld = ldd
								rd = rdd
							else:
								f = 1
						else:
							ld = ld + 1
							rd = rd - 1
							f = 1
					do[i, k] = cnt
					q = d[i, k]
					mi = min(q, cnt)
					som = som + mi
					if rd >= r:
						l = ld
						r = rd
				else:
					cnt = do[j, k]
					do[i, k] = cnt
					q = d[i, k]
					mi = min(q, cnt)
					som = som + mi
					ld = i - cnt + 1
					rd = i + cnt - 1
					if rd >= r:
						l = ld
						r = rd
			i = i + 1
		k = k + 1
	print(som)


T = int(input())
for t in range(T):
	(N, M) = [int(x) for x in input().split()]
	inp = []
	for i in range(N):
		inp.append([int(x) for x in input().split()])
	phor = [[0] * M for i in range(N)]
	pvert = [[0] * M for i in range(N)]
	for i in range(N):
		l = 0
		r = -1
		for j in range(M):
			if j > r:
				k = 1
			else:
				k = min(phor[i][l + r - j], r - j + 1)
			while 0 <= j - k and j + k < M and (inp[i][j - k] == inp[i][j + k]):
				k += 1
			phor[i][j] = k
			k -= 1
			if j + k > r:
				l = j - k
				r = j + k
	for j in range(M):
		l = 0
		r = -1
		for i in range(N):
			if i > r:
				k = 1
			else:
				k = min(pvert[l + r - i][j], r - i + 1)
			while 0 <= i - k and i + k < N and (inp[i - k][j] == inp[i + k][j]):
				k += 1
			pvert[i][j] = k
			k -= 1
			if i + k > r:
				l = i - k
				r = i + k
	summ = 0
	for i in range(N):
		for j in range(M):
			summ += min(phor[i][j], pvert[i][j])
	print(summ)


def longestPalindrome(s):
	l = len(s)
	res = [0] * l
	(c, r) = (0, 0)
	for i in range(l):
		m = 2 * c - i
		if i < r and m >= 0:
			res[i] = min(r - i, res[m])
		try:
			while i + res[i] < l and i - res[i] >= 0 and (s[i + res[i]] == s[i - res[i]]):
				res[i] += 1
		except IndexError as e:
			pass
		if i + res[i] > r:
			c = i
			r = i + res[i]
	return res
for t in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	ldash = []
	ldash = list(map(list, zip(*l)))
	lh = [[0] * m] * n
	ldashh = [[0] * n] * m
	for i in range(n):
		lh[i] = longestPalindrome(l[i])
	for i in range(m):
		ldashh[i] = longestPalindrome(ldash[i])
	ans = 0
	for i in range(n):
		for j in range(m):
			ans += min(lh[i][j], ldashh[j][i])
	print(ans)


def count_matrix(matrix, i, j, n, m):
	l = min(i - 0, n - 1 - i, j - 0, m - 1 - j)
	count = 0
	for k in range(l):
		if matrix[i - k - 1][j] == matrix[i + k + 1][j] and matrix[i][j - k - 1] == matrix[i][j + k + 1]:
			count += 1
		else:
			break
	return count

def find_pairs(matrix, n, m):
	pairs = n * m
	mn = min(n, m)
	l = mn if mn % 2 != 0 else mn - 1
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			pairs += count_matrix(matrix, i, j, n, m)
	return pairs
pairs = []
test_cases = int(input())
for test_case in range(test_cases):
	size = list(map(int, input().strip().split()))
	(n, m) = (size[0], size[1])
	matrix = []
	for i in range(n):
		rows = list(map(int, input().strip().split()))
		matrix.append(rows)
	pairs.append(find_pairs(matrix, n, m))
for pair in pairs:
	print(pair)


from abc import ABC, abstractmethod
import sys
sys.setrecursionlimit(1000000)

def get_int(source):
	return int(source())

def get_ints(source):
	return [int(x) for x in source().split(' ')]

def getline_from_std():
	return input()

class IOProcessing(ABC):

	@abstractmethod
	def read_test_case(self, source):
		pass

	@abstractmethod
	def process_test_case(self, tcase):
		pass

	def solve(self, input_type='from_std', output_type='to_std', input_path='', output_path='output.txt', tcase_handling='all'):
		ans = []
		if input_type == 'from_file':
			with open(input_path, 'r') as in_file:
				t = int(in_file.readline())
				for _ in range(t):
					tcase = self.read_test_case(in_file.readline)
					ans.append(self.process_test_case(tcase))
					if tcase_handling == 'single' and output_type == 'to_std':
						print(ans[-1])
		elif input_type == 'from_std':
			t = int(getline_from_std())
			for _ in range(t):
				tcase = self.read_test_case(getline_from_std)
				ans.append(self.process_test_case(tcase))
				if tcase_handling == 'single' and output_type == 'to_std':
					print(ans[-1])
		if output_type == 'to_file':
			with open(output_path, 'w') as output:
				for a in ans:
					output.write(str(a) + '\n')
		elif output_type == 'to_std' and tcase_handling == 'all':
			for a in ans:
				print(a)

class Ex_1_io(IOProcessing):

	def read_test_case(self, source):
		(n, m) = get_ints(source)
		a = []
		for _ in range(n):
			a.append(get_ints(source))
		return {'n': n, 'm': m, 'a': a}

	def process_test_case(self, tcase):
		n = tcase['n']
		m = tcase['m']
		a = tcase['a']
		ans = 0
		for i in range(n):
			for j in range(m):
				maxd = min(i, j, n - i, m - j)
				l = 0
				while l <= maxd and i - l >= 0 and (i + l < n) and (j - l >= 0) and (j + l < m) and (a[i - l][j] == a[i + l][j]) and (a[i][j - l] == a[i][j + l]):
					l += 1
				ans += l
		return ans
solution = Ex_1_io()
solution.solve(input_type='from_std', output_type='to_std', input_path='input.txt', output_path='output.txt', tcase_handling='all')


from itertools import count

def read_mat(rows, cols):
	mat = [input().split() for _ in range(rows)]
	return mat

def noof_pairs(mat, rows, cols):
	noof_elems = rows * cols
	cnt = 0
	for i in range(1, rows - 1):
		for j in range(1, cols - 1):
			for k in count(1):
				if i - k >= 0 and j - k >= 0 and (i + k < rows) and (j + k < cols):
					pass
				else:
					break
				if mat[i][j - k] == mat[i][j + k] and mat[i - k][j] == mat[i + k][j]:
					cnt += 1
				else:
					break
	return cnt + noof_elems

def main():
	for i in range(int(input())):
		(rows, cols) = map(int, input().split())
		mat = read_mat(rows, cols)
		cnt = noof_pairs(mat, rows, cols)
		print(cnt)
main()


pali = lambda x: x == x[::-1]

def traverse(arr, n, m):
	cnt = m * n
	for i in range(n):
		for j in range(m):
			length = 2 * min(i, j, n - i - 1, m - j - 1) + 1
			if length == 1:
				continue
			if i < length // 2 or i >= n - length // 2 or j < length // 2 or (j >= m - length // 2):
				continue
			for x in range(1, length // 2 + 1):
				if arr[i - x][j] == arr[i + x][j] and arr[i][j - x] == arr[i][j + x]:
					cnt += 1
				else:
					break
	return cnt

def brute(arr, m, n):
	res = 0
	res += traverse(arr, n, m)
	return res
for t in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
	print(brute(arr, m, n))


def maxPall(text):
	g = [0] * len(text)
	(c, r) = (0, 0)
	l = len(text)
	for i in range(0, len(text)):
		mirror = 2 * c - i
		if mirror >= 0 and i < r:
			g[i] = min(r - i, g[mirror])
		try:
			while i + g[i] < l and i - g[i] >= 0 and (text[i + g[i]] == text[i - g[i]]):
				g[i] += 1
		except IndexError as e:
			pass
		if i + g[i] > r:
			c = i
			r = i + g[i]
	return g
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ar = []
	for i in range(n):
		ar.append(list(map(int, input().split())))
	rowPal = []
	colPal = []
	for i in range(n):
		rowPal.append(maxPall(ar[i]))
	arr = list(map(list, zip(*ar)))
	for i in range(m):
		colPal.append(maxPall(arr[i]))
	colPal = list(map(list, zip(*colPal)))
	g = 0
	for i in range(n):
		for j in range(m):
			g += min(rowPal[i][j], colPal[i][j])
	print(g)


import numpy as np
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	matrix = []
	for i in range(n):
		temp = list(map(int, input().split()))
		matrix.append(temp)
	ans = 0
	rows = np.zeros((n, m))
	for row in range(n):
		l = 0
		r = -1
		for i in range(m):
			if i > r:
				k = 1
			else:
				k = min(rows[row][l + r - i], 1 + r - i)
				k = int(k)
			while 0 <= i - k and i + k < m and (matrix[row][i - k] == matrix[row][i + k]):
				k += 1
			rows[row][i] = k
			k -= 1
			if i + k > r:
				l = i - k
				r = i + k
	cols = np.zeros((n, m))
	for col in range(m):
		l = 0
		r = -1
		for i in range(n):
			if i > r:
				k = 1
			else:
				k = min(cols[l + r - i][col], 1 + r - i)
				k = int(k)
			while 0 <= i - k and i + k < n and (matrix[i - k][col] == matrix[i + k][col]):
				k += 1
			cols[i][col] = k
			ans += min(rows[i][col], k)
			kk = k - 1
			if i + kk > r:
				l = i - kk
				r = i + kk
	ans = 0
	for i in range(n):
		for j in range(m):
			ans += min(rows[i][j], cols[i][j])
	print(int(ans))


def pairs(matrix, n, m):
	pairs = n * m
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			for k in range(min(min(n - i - 1, i), min(m - j - 1, j))):
				k += 1
				if matrix[i - k][j] == matrix[i + k][j] and matrix[i][j + k] == matrix[i][j - k]:
					pairs += 1
				else:
					break
	return pairs
for test in range(int(input())):
	(N, M) = [int(x) for x in input().split()]
	MATRIX = [[int(x) for x in input().split()] for x in range(N)]
	print(pairs(MATRIX, N, M))


def check(x, i, j, y):
	r = 0
	count = 0
	while r <= y:
		if x[i][j - r] == x[i][j + r] and x[i - r][j] == x[i + r][j]:
			count += 1
		else:
			return count
		r += 1
	return count
t = int(input())
while t > 0:
	(n, m) = [int(x) for x in input().split()]
	matrix = []
	for i in range(n):
		a = [int(y) for y in input().split()]
		matrix.append(a)
		m = len(a)
	final = 0
	for i in range(n):
		for j in range(m):
			temp1 = 1000000
			temp2 = 1000000
			if i >= n / 2:
				temp1 = n - 1 - i
			if j >= m / 2:
				temp2 = m - j - 1
			temp = min(i, j, temp1, temp2)
			final = final + check(matrix, i, j, temp)
	print(final)
	t -= 1


def manachars(arr, n, l):
	n = 2 * n + 1
	c = 1
	r = 2
	diff = -1
	imirror = -1
	l[1] = 1
	for i in range(2, n):
		imirror = 2 * c - i
		diff = r - i
		if diff > 0:
			l[i] = min(diff, l[imirror])
		try:
			while i + l[i] < n and i - l[i] > 0 and ((i + l[i] + 1) % 2 == 0 or arr[(i - l[i] - 1) // 2] == arr[(i + l[i] + 1) // 2]):
				l[i] += 1
		except:
			pass
		if i + l[i] > r:
			c = i
			r = i + l[i]
try:
	t = int(input())
	for _ in range(t):
		(n, m) = list(map(int, input().split()))
		arr = []
		arrtrans = [[0 for i in range(n)] for j in range(m)]
		for i in range(n):
			x = list(map(int, input().split()))
			arr.append(x)
			for j in range(m):
				arrtrans[j][i] = arr[i][j]
		ans = 0
		l = [[0 for i in range(2 * m + 1)] for j in range(n)]
		for i in range(n):
			manachars(arr[i], m, l[i])
		l1 = [[0 for i in range(2 * n + 1)] for j in range(m)]
		for j in range(m):
			manachars(arrtrans[j], n, l1[j])
		ans = 0
		for i in range(n):
			for j in range(m):
				a = 2 * i + 1
				b = 2 * j + 1
				ans += (min(l[i][b], l1[j][a]) - 1) // 2
		print(m * n + ans)
except:
	pass


import math

def LPS(A):
	T = ['$', '#']
	for a in A:
		T.append(a)
		T.append('#')
	T.append('@')
	P = [0] * len(T)
	(C, R) = (0, 0)
	for i in range(1, len(T)):
		mirr = 2 * C - i
		if i < R:
			P[i] = min(R - i, P[mirr])
		try:
			if i - (1 + P[i]) < 0:
				raise IndexError
			while T[i + (1 + P[i])] == T[i - (1 + P[i])]:
				P[i] += 1
		except IndexError:
			pass
		if i + P[i] > R:
			C = i
			R = i + P[i]
	X = []
	for i in range(len(T)):
		if T[i] != '$' and T[i] != '@' and (T[i] != '#'):
			X.append(P[i])
	return X
test = int(input())
for t in range(test):
	arr = list()
	(n, m) = map(int, input().split())
	for i in range(n):
		arr.append(list(map(int, input().split())))
	rowCount = [[0] * m for i in range(n)]
	for i in range(n):
		sol = LPS(arr[i])
		for j in range(m):
			rowCount[i][j] = sol[j]
	colCount = [[0] * m for i in range(n)]
	for j in range(m):
		A = []
		for i in range(n):
			A.append(arr[i][j])
		sol = LPS(A)
		for i in range(n):
			colCount[i][j] = sol[i]
	count = 0
	for i in range(n):
		for j in range(m):
			count += math.ceil(min(rowCount[i][j], colCount[i][j]) / 2)
	print(count)