Chef has just finished the construction of his new garden. He has sown the garden with patches of the most beautiful carpet grass he could find. He has filled it with patches of different color and now he wants to evaluate how elegant his garden is.
Chef's garden looks like a rectangular grid of cells with N rows and M columns. So there are N x M cells in total.	In each cell Chef planted grass of some color.
The elegance of the garden is defined by the number of squares, composed of at least four  garden cells, with edges parallel to the sides of the garden, that have four corner cells of the same color.
Given the description of Chef's garden, calculate how many such squares exist.
Input format
The first line contains the number T, the number of test cases. In the following lines,	T test cases follow (without any newlines between them.)
The first line of each test case contains N and M, separated by a single space.
Each of the next N lines contains M characters without any spaces between them, and without any leading or trailing spaces.
Each character describes the color of the corresponding cell in the garden and belongs to the set of lowercase and uppercase lettes of the English alphabet.
One letter in lowercase and uppercase describes different colors.
Output format
For each test case, print the number of squares that conform to the definition in the	problem statement.
Constraints
1 ≤ T ≤ 50

1 ≤ N, M ≤ 50

Sample input
3
2 2
aa
aA
3 3
aba
bab
aba
4 4
aabb
aabb
bbaa
bbaa

Sample output
0
1
4

Explanation
In the first case the only avaliable square does not conform to the definition in the problem statement because 'a' and 'A' describes different colors.
In the second case, you can select the 4 a's at the corners of the garden.
In the third case, you can only make four squares, from the four 2x2 segments	that are of the same color.

Difficulty: EASY
Tags: Greedy algorithms

Complete search

Constructive algorithms

Ad-hoc
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
T = int(input())

def algo():
	(N, M) = map(int, input().split())
	li = []
	for i in range(N):
		li.append(input())
	out = 0
	q = 0
	while q < M:
		p = 0
		while p < N:
			f = min(N - p - 1, M - q - 1)
			if f == 0:
				break
			else:
				for j in range(1, f + 1):
					if li[p][q] == li[p + j][q] == li[p][q + j] == li[p + j][q + j]:
						out += 1
			p += 1
		q += 1
	print(out)
for i in range(T):
	algo()


t = int(input())
for ni in range(t):
	(n, m) = map(int, input().split())
	l = list()
	for ki in range(n):
		l.append(input())
		(k, s) = (0, 0)
	for i in range(n - 1):
		for j in range(m - 1):
			k = j + 1
			while k < m and i + k - j < n:
				if l[i][j] == l[i][k] == l[i + k - j][j] == l[i + k - j][k]:
					s = s + 1
				k = k + 1
	print(s)


def garden(n, m):
	c = 0
	for i in range(n):
		for j in range(m):
			b = a[i][j]
			len = 1
			while i + len < n and j + len < m:
				if a[i][j + len] == b and a[i + len][j] == a[i + len][j + len] and (a[i + len][j] == b):
					c += 1
				len += 1
	return c
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(input()))
	print(garden(n, m))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = []
	count = 0
	for i in range(n):
		l.append(input())
	for i in range(n - 1):
		for j in range(m - 1):
			l1 = min(n - i, m - j)
			for k in range(1, l1):
				if l[i][j] == l[i + k][j] and l[i][j] == l[i][j + k] and (l[i][j] == l[i + k][j + k]):
					count += 1
	print(count)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	o = 0
	for _ in range(n):
		s = input()
		l.append(s)
	for i in range(n):
		for j in range(m):
			q = i + 1
			w = j + 1
			while q < n and w < m:
				p = l[i][j]
				if l[i][w] == p and l[q][j] == l[q][w] and (l[q][j] == p):
					o = o + 1
				q = q + 1
				w = w + 1
	print(o)


t = int(input())
for _ in range(t):
	line = input().split()
	n = int(line[0])
	m = int(line[1])
	garden = []
	for _ in range(n):
		garden.append(list(input()))
	count = 0
	for i in range(n - 1):
		for j in range(m - 1):
			for side in range(1, min(n - i, m - j)):
				upper_l = garden[i][j]
				upper_r = garden[i][j + side]
				bottom_l = garden[i + side][j]
				bottom_r = garden[i + side][j + side]
				if upper_r == upper_l == bottom_l == bottom_r:
					count += 1
	print(count)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	c = 0
	for i in range(n):
		a = input()
		l.append(a)
	for i in range(n - 1):
		for j in range(m - 1):
			for k in range(1, min(n - i, m - j)):
				if l[i][j] == l[i + k][j] and l[i][j] == l[i][j + k] and (l[i][j] == l[i + k][j + k]):
					c += 1
	print(c)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	flowers = []
	for i in range(n):
		flowers.append(input())
	c = 0
	for i in range(n):
		for j in range(m):
			k = 1
			while k + j < m and k + i < n:
				if flowers[i][j] == flowers[i + k][j] and flowers[i][j] == flowers[i][j + k] and (flowers[i][j] == flowers[i + k][j + k]):
					c += 1
				k += 1
	print(c)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		x = input()
		s = []
		s[:] = x
		a.append(s)
	count = 0
	for i in range(n):
		for j in range(m):
			if m - j > n - i:
				min = n - i
			else:
				min = m - j
			for k in range(1, min):
				if a[i][j] == a[i + k][j] == a[i + k][j + k] == a[i][j + k]:
					count += 1
	print(count)


def solve(A, N, M):
	ans = 0
	for i in range(0, N - 1):
		for j in range(0, M - 1):
			(delta, ch) = (1, A[i][j])
			while i + delta < N and j + delta < M:
				if A[i][j + delta] == ch and A[i + delta][j] == ch and (A[i + delta][j + delta] == ch):
					ans += 1
				delta += 1
	print(ans)
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	A = []
	for i in range(N):
		row = input()
		A.append(row)
	solve(A, N, M)


t = int(input())
for _ in range(t):
	(N, M) = map(int, input().split())
	matrix = []
	for i in range(N):
		row = []
		l = input()
		for j in range(M):
			element = l[j]
			row.append(element)
		matrix.append(row)
	ans = 0
	for i in range(N):
		for j in range(M):
			same = matrix[i][j]
			delta = 1
			while i + delta < N and j + delta < M:
				if matrix[i + delta][j] == same and matrix[i][j + delta] == same and (matrix[i + delta][j + delta] == same):
					ans += 1
				delta += 1
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	matrix = []
	for i in range(n):
		matrix.append(input())
	count = 0
	for r in range(n):
		for c in range(m):
			ar = r + 1
			ac = c + 1
			while ar < n and ac < m:
				cs = matrix[r][c]
				if matrix[ar][c] == cs and matrix[ar][ac] == cs and (matrix[r][ac] == cs):
					count += 1
				ar += 1
				ac += 1
	print(count)


tests = int(input())
for i in range(tests):
	(n, m) = map(int, input().split())
	arr = []
	ans = 0
	for i in range(n):
		arr.append(input())
	for x in range(n - 1):
		for y in range(m - 1):
			temp = arr[x][y]
			start = 1
			if n - x > m - y:
				end = m - y
			else:
				end = n - x
			for z in range(start, end):
				if temp == arr[x][y + z] == arr[x + z][y] == arr[x + z][y + z]:
					ans += 1
	print(ans)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = []
	count = 0
	for i in range(a):
		s = input()
		l.append(s)
	for j in range(a - 1):
		for m in range(b - 1):
			for n in range(1, min(a - j, b - m)):
				if l[j][m] == l[j + n][m] and l[j][m] == l[j][m + n] and (l[j][m] == l[j + n][m + n]):
					count += 1
	print(count)


def solve(a, n, m):
	ans = 0
	for i in range(0, n - 1):
		for j in range(0, m - 1):
			(delta, ch) = (1, a[i][j])
			while i + delta < n and j + delta < m:
				if a[i][j + delta] == ch and a[i + delta][j] == ch and (a[i + delta][j + delta] == ch):
					ans += 1
				delta += 1
	print(ans)
for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(input())
	solve(a, n, m)


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	g = []
	for i in range(n):
		g.append(str(input()))
	c = 0
	for i in range(n):
		for j in range(m):
			k = 1
			while k + j < m and k + i < n:
				if g[i][j] == g[i + k][j] and g[i][j] == g[i][j + k] and (g[i][j] == g[i + k][j + k]):
					c += 1
				k += 1
	print(c)


for _ in range(int(input())):
	(N, M) = [int(x) for x in input().split()]
	List = []
	for i in range(N):
		Temp = [x for x in input()]
		List.append(Temp)
	Ans = 0
	for i in range(N):
		for j in range(M):
			x = 1
			while i + x < N and j + x < M:
				if List[i][j] == List[i][j + x] == List[i + x][j] == List[i + x][j + x]:
					Ans += 1
				x += 1
	print(Ans)


t = int(input())
while t != 0:
	(n, m) = map(int, input().split())
	l = []
	for x in range(0, n):
		ls = []
		ls.extend(input())
		l.append(ls)
	s = 0
	for i in range(0, n - 1):
		for j in range(0, m - 1):
			k = j + 1
			while k < m and i + k - j < n:
				if l[i][j] == l[i][k] == l[i + k - j][j] == l[i + k - j][k]:
					s += 1
				k += 1
	print(s)
	t -= 1


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	ls = []
	for i in range(x):
		s = input()
		ls.append(s)
	cnt = 0
	for i in range(x - 1):
		for j in range(y - 1):
			ele = ls[i][j]
			for k in range(j + 1, y):
				if ele == ls[i][k]:
					dist = k - j
					if i + dist < x and j + dist < y:
						if ls[i + dist][j] == ele and ls[i + dist][j + dist] == ele:
							cnt += 1
					else:
						break
	print(cnt)


def check_square(arr, nn, mm):
	total = 0
	for dim in range(2, mm + 1):
		for row in range(nn - dim + 1):
			for col in range(mm - dim + 1):
				if arr[row][col] == arr[row][col + dim - 1] == arr[row + dim - 1][col] == arr[row + dim - 1][col + dim - 1]:
					total += 1
	return total
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	garden = []
	for i in range(n):
		garden.append(input())
	if n == 1 or m == 1:
		print(0)
	else:
		print(check_square(garden, n, m))


t = int(input())
while t:
	(n, m) = map(int, input().split())
	li = []
	for i in range(n):
		li.append(input())
	counter = 0
	for i in range(n - 1):
		for j in range(m - 1):
			l = min(n - i, m - j)
			for k in range(1, l):
				if li[i][j] == li[i + k][j] and li[i][j] == li[i][j + k] and (li[i][j] == li[i + k][j + k]):
					counter += 1
	print(counter)
	t -= 1


import sys
import math

def main(grid):
	ans = 0
	for i in range(len(grid)):
		for j in range(len(grid[0])):
			first_point = grid[i][j]
			for k in range(j + 1, len(grid[0])):
				second_point = grid[i][k]
				if first_point == second_point:
					dist = k - j
					if i + dist < len(grid):
						thrid_point = grid[i + dist][j]
						fourth_point = grid[i + dist][k]
						if second_point == thrid_point and second_point == fourth_point:
							ans += 1
	return ans
test = int(input())
for _ in range(test):
	(n, m) = input().split()
	n = int(n)
	arr = []
	for b in range(n):
		arr.append(list(input()))
	print(main(arr))


def gard(n, m):
	ans = 0
	for i in range(n):
		for j in range(m):
			k = i + 1
			l = j + 1
			while k < n and l < m:
				b = a[i][j]
				if a[i][l] == b and a[k][j] == a[k][l] and (a[k][j] == b):
					ans += 1
				k += 1
				l += 1
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(input()))
	print(gard(n, m))


for t in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append(list(input()))
	k = min(m, n)
	sum = 0
	for i in range(n):
		for j in range(m):
			c = 1
			while i + c < n and j + c < m:
				if l[i][j] == l[i + c][j] == l[i][j + c] == l[i + c][j + c]:
					sum += 1
				c += 1
	print(sum)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	grid = [input() for _ in range(a)]
	count = 0
	for x in range(a):
		for y in range(b):
			for w in range(1, min(b - y, a - x)):
				xf = w + x
				yf = w + y
				if xf >= a or yf >= b:
					pass
				else:
					count += grid[x][y] == grid[x][yf] == grid[xf][y] == grid[xf][yf]
	print(count)


for tc in range(int(input())):
	(n, m) = map(int, input().split())
	s = []
	for i in range(n):
		s.append(input())
	cnt = 0
	for size in range(2, min(n, m) + 1):
		for startcol in range(m - size + 1):
			for startrow in range(n - size + 1):
				ul = s[startrow][startcol]
				ur = s[startrow][startcol + size - 1]
				ll = s[startrow + size - 1][startcol]
				lr = s[startrow + size - 1][startcol + size - 1]
				if ul == ur and ur == ll and (ll == lr):
					cnt += 1
	print(cnt)


t = int(input())
ans = []
for _ in range(t):
	(N, M) = map(int, input().split())
	A = []
	for i in range(N):
		x = list(input())
		A.append(x)
	count = 0
	for i in range(2, min(N, M) + 1):
		for j in range(N - i + 1):
			for k in range(M - i + 1):
				if A[j][k] == A[j + i - 1][k] and A[j][k] == A[j][k + i - 1] and (A[j][k] == A[j + i - 1][k + i - 1]):
					count += 1
	ans.append(count)
for i in ans:
	print(i)


T = int(input())
ans = []
for i in range(T):
	(N, M) = [int(i) for i in input().split()]
	A = []
	for i in range(N):
		x = list(input())
		A.append(x)
	count = 0
	for s in range(2, min(N, M) + 1):
		for i in range(N - s + 1):
			for j in range(M - s + 1):
				if A[i][j] == A[i + s - 1][j] and A[i][j] == A[i][j + s - 1] and (A[i][j] == A[i + s - 1][j + s - 1]):
					count += 1
	ans.append(count)
for i in ans:
	print(i)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	x = []
	for val in range(n):
		x.append(list(map(str, input())))
	count = 0
	for size in range(1, min(n, m)):
		for i in range(0, n - size):
			for j in range(0, m - size):
				if x[i][j] == x[i][j + size] and x[i + size][j] == x[i + size][j + size] and (x[i][j] == x[i + size][j]):
					count += 1
	print(count)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	matrix = []
	for i in range(n):
		row = []
		l = input()
		for j in range(m):
			ele = l[j]
			row.append(ele)
		matrix.append(row)
	ans = 0
	for i in range(n):
		for j in range(m):
			same = matrix[i][j]
			delta = 1
			while i + delta < n and j + delta < m:
				if matrix[i][j + delta] == same and matrix[i + delta][j] == same and (matrix[i + delta][j + delta] == same):
					ans = ans + 1
				delta = delta + 1
	print(ans)


def garden(n, m):
	ans = 0
	for i in range(n):
		for j in range(m):
			s = arr[i][j]
			len = 1
			while i + len < n and j + len < m:
				if arr[i][j + len] == s and arr[i + len][j] == arr[i + len][j + len] and (arr[i + len][j] == s):
					ans += 1
				len += 1
	return ans
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(list(input()))
	print(garden(n, m))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lst = []
	for _ in range(n):
		lst.append(input())
	count = 0
	for i in range(n):
		for j in range(m):
			c = 1
			while c + j < m and c + i < n:
				if lst[i][j] == lst[i + c][j] and lst[i][j] == lst[i][j + c] and (lst[i][j] == lst[i + c][j + c]):
					count += 1
				c += 1
	print(count)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	garden = []
	for i in range(n):
		garden += [input()]
	sq = 0
	for x in range(m - 1):
		for y in range(n - 1):
			x2 = x + 1
			y2 = y + 1
			while x2 < m and y2 < n:
				if garden[y][x] == garden[y][x2]:
					if garden[y][x] == garden[y2][x]:
						if garden[y][x] == garden[y2][x2]:
							sq += 1
				x2 += 1
				y2 += 1
	print(sq)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	array = []
	for i in range(N):
		array.append(list(input().strip()))
	count = 0
	for i in range(N - 1):
		for j in range(M - 1):
			for k in range(j + 1, min(j + N - i, M)):
				if array[i][j] == array[i][k] and array[i][j] == array[i + k - j][j] and (array[i][j] == array[i + k - j][k]):
					count += 1
	print(count)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(input())
	ans = 0
	length = 1
	while length <= min([n, m]):
		for x in range(0, n - length):
			for y in range(0, m - length):
				if a[x][y] == a[x + length][y] and a[x][y] == a[x][y + length] and (a[x][y] == a[x + length][y + length]):
					ans += 1
		length += 1
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	garden = []
	for i in range(n):
		garden.append([i for i in input()])
	count = 0
	for size in range(1, min(n, m)):
		for i in range(0, n - size):
			for j in range(0, m - size):
				if garden[i][j] == garden[i][j + size] and garden[i + size][j] == garden[i + size][j + size] and (garden[i][j] == garden[i + size][j]):
					count += 1
	print(count)


def temp(arr, n, m):
	count = 0
	for i in range(n - 1):
		for j in range(m - 1):
			maxSize = min(n - i, m - j)
			for size in range(1, maxSize):
				if arr[i][j] == arr[i][j + size] == arr[i + size][j] == arr[i + size][j + size]:
					count += 1
	return count
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	A = []
	for i in range(N):
		A.append(input().strip())
	print(temp(A, N, M))


def check(z, i, j, r):
	x = j - i
	if r[z][i] == r[z][j] == r[z + x][i] == r[z + x][j]:
		return True
	return False
t = int(input())
while t:
	t -= 1
	count = 0
	a = list(map(int, input().split()))
	r = []
	for h in range(a[0]):
		p = list(input())
		r.append(p)
	for z in range(a[0]):
		for i in range(a[1]):
			for j in range(i + 1, a[1]):
				x = j - i
				if x <= a[0] - z - 1:
					if check(z, i, j, r) == True:
						count += 1
				else:
					break
	print(count)