You are given a matrix consisting of $n$ rows and $m$ columns. Each cell of this matrix contains $0$ or $1$.

Let's call a square of size $2 \times 2$ without one corner cell an L-shape figure. In one operation you can take one L-shape figure, with at least one cell containing $1$ and replace all numbers in it with zeroes.

Find the maximum number of operations that you can do with the given matrix.


-----Input-----

The first line contains one integer $t$ ($1 \leq t \leq 500$) — the number of test cases. Then follow the descriptions of each test case.

The first line of each test case contains two integers $n$ and $m$ ($2 \leq n, m \leq 500$) — the size of the matrix.

Each of the following $n$ lines contains a binary string of length $m$ — the description of the matrix.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases does not exceed $1000$.


-----Output-----

For each test case output the maximum number of operations you can do with the given matrix.


-----Examples-----

Input
4
4 3
101
111
011
110
3 4
1110
0111
0111
2 2
00
00
2 2
11
11
Output
8
9
0
2


-----Note-----

In the first testcase one of the optimal sequences of operations is the following (bold font shows l-shape figure on which operation was performed):

Matrix before any operation was performed:

1

0

1

1

1

1

0

1

1

1

1

0

Matrix after $1$ operation was performed:

1

0

0

1

0

1

0

1

1

1

1

0

Matrix after $2$ operations were performed:

1

0

0

1

0

0

0

1

1

1

1

0

Matrix after $3$ operations were performed:

1

0

0

1

0

0

0

1

0

1

1

0

Matrix after $4$ operations were performed:

1

0

0

0

0

0

0

1

0

1

1

0

Matrix after $5$ operations were performed:

1

0

0

0

0

0

0

1

0

1

0

0

Matrix after $6$ operations were performed:

1

0

0

0

0

0

0

0

0

1

0

0

Matrix after $7$ operations were performed:

0

0

0

0

0

0

0

0

0

1

0

0

Matrix after $8$ operations were performed:

0

0

0

0

0

0

0

0

0

0

0

0

In the third testcase from the sample we can not perform any operation because the matrix doesn't contain any ones.

In the fourth testcase it does not matter which L-shape figure we pick in our first operation. We will always be left with single one. So we will perform $2$ operations.

Source: codeforces | Difficulty: EASY
Tags: Implementation

Greedy algorithms


Solutions:
g = lambda : [*map(int, input().split())]
for _ in range(int(input())):
	(N, M) = g()
	ones = 0
	Map = []
	for _ in range(N):
		s = input()
		Map.append(s)
		ones += s.count('1')
	if ones == N * M:
		print(ones - 2)
	else:
		flag = False
		for i in range(N - 1):
			for j in range(M - 1):
				if (Map[i][j:j + 2] + Map[i + 1][j:j + 2]).count('0') > 1:
					flag = True
					break
			if flag:
				break
		if flag:
			print(ones)
		else:
			print(ones - 1)


testnum = int(input())
for testcount in range(testnum):
	(n, m) = map(int, input().split())
	znum = 0
	dz = False
	l = []
	for i in range(n):
		s = input()
		znum += s.count('0')
		if not dz:
			l.append('1' + s + '1')
			if s.find('00') >= 0:
				dz = True
	if znum <= 1:
		print(n * m - 2)
		continue
	for i in range(n - 1):
		if dz:
			break
		for j in range(1, m + 1):
			if l[i][j] == '0' and l[i + 1][j - 1:j + 2].find('0') >= 0:
				dz = True
				break
	if dz:
		print(n * m - znum)
	else:
		print(n * m - znum - 1)


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	a = []
	for i in range(n):
		a.append(input())
	count = 0
	for row in a:
		for j in row:
			if j == '1':
				count += 1
	if count == n * m:
		print(count - 2)
		continue
	if count == n * m - 1:
		print(count - 1)
		continue
	flag = False
	for i in range(1, n):
		for j in range(1, m):
			if (a[i - 1][j - 1] == '0') + (a[i - 1][j] == '0') + (a[i][j - 1] == '0') + (a[i][j] == '0') + 0 > 1:
				flag = True
				break
		if flag:
			break
	if flag:
		print(count)
	else:
		print(count - 1)


a = int(input())
for x in range(a):
	(b, c) = map(int, input().split())
	j = []
	s = 0
	for y in range(b):
		d = input()
		s += d.count('1')
		j.append(d)
	p = 0
	q = 0
	for y in range(b):
		for z in range(c):
			if j[y][z] == '0':
				p = -1
				if z - 1 >= 0 and y - 1 >= 0:
					if j[y - 1][z - 1] == '0':
						q = -1
						break
				if z + 1 < c and y + 1 < b:
					if j[y + 1][z + 1] == '0':
						q = -1
						break
				if z - 1 >= 0 and y + 1 < b:
					if j[y + 1][z - 1] == '0':
						q = -1
						break
				if z + 1 < c and y - 1 >= 0:
					if j[y - 1][z + 1] == '0':
						q = -1
						break
				if z - 1 >= 0:
					if j[y][z - 1] == '0':
						q = -1
						break
				if y - 1 >= 0:
					if j[y - 1][z] == '0':
						q = -1
						break
				if y + 1 < b:
					if j[y + 1][z] == '0':
						q = -1
						break
				if z + 1 < c:
					if j[y][z + 1] == '0':
						q = -1
						break
	if q == -1:
		print(s)
	elif p == -1:
		print(s - 1)
	else:
		print(s - 2)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	matrix = []
	ones = False
	zeros = False
	ops = 0
	for _ in range(x):
		s = input().strip()
		ops += s.count('1')
		if '1' in s:
			ones = True
		if '0' in s:
			zeros = True
		matrix.append([j for j in s])
	if not ones:
		print(0)
		continue
	if not zeros:
		print(ops - 2)
		continue
	ops -= 1
	flag = False
	for i in range(x - 1):
		for j in range(y - 1):
			count = 0
			if matrix[i][j] == '0':
				count += 1
			if matrix[i + 1][j] == '0':
				count += 1
			if matrix[i + 1][j + 1] == '0':
				count += 1
			if matrix[i][j + 1] == '0':
				count += 1
			if count >= 2:
				ops += 1
				flag = True
				break
		if flag:
			break
	print(ops)


import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	a = []
	ones = 0
	flag = 0
	for i in range(n):
		s = input().strip()
		a.append(s)
		ones += s.count('1')
		if i == 0:
			if '00' in s:
				flag = 1

	def check(i, j):
		if 0 <= i <= n - 1 and 0 <= j <= m - 1 and (a[i][j] == '0'):
			return True
		return False
	for i in range(n):
		for j in range(m):
			if a[i][j] == '0':
				if check(i, j + 1) or check(i, j - 1) or check(i - 1, j) or check(i + 1, j) or check(i + 1, j + 1) or check(i + 1, j - 1) or check(i - 1, j + 1) or check(i - 1, j + 1):
					flag = 1
					break
	for i in range(n - 1):
		if a[i][0] == a[i + 1][0] == '0':
			flag = 1
	if flag == 0:
		if ones == m * n:
			ans = ones - 2
		elif ones == 0:
			ans = 0
		else:
			ans = ones - 1
	else:
		ans = ones
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = [0] * n
	for i in range(n):
		a[i] = list(input())
	count = 0
	for row in a:
		for v in row:
			if v == '1':
				count += 1
	if count == n * m:
		print(count - 2)
		continue
	if count == n * m - 1:
		print(count - 1)
		continue
	flag = False
	for i in range(1, n):
		for j in range(1, m):
			if 1 < 0 + (a[i - 1][j - 1] == '0') + (a[i - 1][j] == '0') + (a[i][j - 1] == '0') + (a[i][j] == '0'):
				flag = True
				break
		if flag:
			break
	if flag:
		print(count)
	else:
		print(count - 1)


t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	d = [list(map(int, input())) for x in range(n)]
	c = sum((sum(r) for r in d))
	perfect = False
	if c == n * m:
		print(c - 2)
	elif c == 0:
		print(0)
	else:
		for p in range(n - 1):
			for q in range(m - 1):
				s = d[p][q] + d[p][q + 1] + d[p + 1][q] + d[p + 1][q + 1]
				if s <= 2:
					perfect = True
					break
			if perfect:
				break
		print(c if perfect else c - 1)


t = int(input())
res = []
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	a = []
	s = 0
	for _ in range(n):
		a.append(list(map(int, input())))
		s += sum(a[-1])
	if s == n * m:
		res.append(s - 2)
	elif s == 0:
		res.append(0)
	else:
		L = False
		for i in range(n):
			for j in range(m):
				if i + 1 < n and a[i][j] == 0 and (a[i + 1][j] == 0):
					L = True
					break
				if j + 1 < m and a[i][j] == 0 and (a[i][j + 1] == 0):
					L = True
					break
				if j + 1 < m and a[i][j + 1] == 0 and (i + 1 < n) and (a[i + 1][j] == 0):
					L = True
					break
				if j - 1 > -1 and a[i][j - 1] == 0 and (i + 1 < n) and (a[i + 1][j] == 0):
					L = True
					break
				if i - 1 > -1 and a[i - 1][j] == 0 and (j + 1 < m) and (a[i][j + 1] == 0):
					L = True
					break
				if i - 1 > -1 and a[i - 1][j] == 0 and (j - 1 > -1) and (a[i][j - 1] == 0):
					L = True
					break
		if L:
			res.append(s)
		else:
			res.append(s - 1)
for r in res:
	print(r)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	grid = []
	direction = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
	ones = 0
	zeros = 0
	for _ in range(n):
		grid.append(list(input()))
		ones += grid[-1].count('1')
		zeros += grid[-1].count('0')
	found = False
	for r in range(n):
		for c in range(m):
			if grid[r][c] == '0':
				for (dx, dy) in direction:
					(newr, newc) = (r + dx, c + dy)
					if 0 <= newr < n and 0 <= newc < m:
						if grid[newr][newc] == '0':
							found = True
							break
				if found:
					break
		if found:
			break
	if found:
		print(ones)
	elif zeros > 0:
		print(ones - 1)
	else:
		print(ones - 2)


t = int(input())
for iteration in range(t):
	(n, m) = tuple(map(int, input().split()))
	rows = []
	weight = 0
	for i in range(n):
		row = input()
		weight += sum(list(map(int, list(row))))
		rows.append(row)
	if weight == n * m:
		print(n * m - 2)
	else:
		double_zero = False
		for i in range(n - 1):
			for j in range(m - 1):
				zero_count = 0
				for k in (i, i + 1):
					for l in (j, j + 1):
						if rows[k][l] == '0':
							zero_count += 1
				if zero_count >= 2:
					double_zero = True
					break
			if double_zero:
				break
		if double_zero:
			print(weight)
		else:
			print(weight - 1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [list(map(int, input())) for i in range(n)]
	ones = sum(map(sum, a))
	if ones == n * m:
		print(ones - 2)
	else:
		is_2_0 = False
		for row in range(n):
			for col in range(1, m):
				if a[row][col] == 0 and (a[row][col - 1] == 0 or (row and a[row - 1][col - 1] == 0)):
					is_2_0 = True
					break
			if is_2_0:
				break
		if not is_2_0:
			for col in range(m):
				for row in range(1, n):
					if a[row][col] == 0 and (a[row - 1][col] == 0 or (col < m - 1 and a[row - 1][col + 1] == 0)):
						is_2_0 = True
						break
				if is_2_0:
					break
		if is_2_0:
			print(ones)
		else:
			print(ones - 1)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve():
	(n, m) = inlt()
	matrix = []
	for _ in range(n):
		matrix.append(insr())
	one = 0
	for i in range(n):
		for j in range(m):
			if matrix[i][j] == '1':
				one += 1
	zero = 0
	for i in range(n):
		for j in range(m):
			if matrix[i][j] == '0':
				zero += 1
				for (ni, nj) in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1], [i - 1, j - 1], [i - 1, j + 1], [i + 1, j - 1], [i + 1, j + 1]]:
					if 0 <= ni < n and 0 <= nj < m and (matrix[ni][nj] == '0'):
						return one
	if zero == 0:
		return one - 2
	return one - 1
for _ in range(inp()):
	print(solve())


def e(arr, i, j):
	if i < 0 or i >= len(arr):
		return -1
	if j < 0 or j >= len(arr[i]):
		return -1
	return arr[i][j]
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [input() for __ in range(n)]
	adjacent = False
	diagonal = False
	ones = 0
	for (i, r) in enumerate(a):
		for (j, x) in enumerate(r):
			if x == '0' and (not (adjacent or diagonal)):
				if e(a, i, j + 1) == '0' or e(a, i, j - 1) == '0' or e(a, i - 1, j) == '0' or (e(a, i + 1, j) == '0'):
					adjacent = True
				if e(a, i - 1, j - 1) == '0' or e(a, i - 1, j + 1) == '0' or e(a, i + 1, j - 1) == '0' or (e(a, i + 1, j + 1) == '0'):
					diagonal = True
			elif x == '1':
				ones += 1
	if adjacent or diagonal:
		print(ones)
	elif ones == n * m:
		print(ones - 2)
	else:
		print(ones - 1)


DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]

def main():
	length = int(input())
	for _ in range(length):
		(row, col) = list(map(int, input().split(' ')))
		graph = []
		for _ in range(row):
			line = input()
			graph.append(line)
		res = solver(graph, row, col)
		sum_val = 0
		for r in range(row):
			for c in range(col):
				if graph[r][c] == '1':
					sum_val += 1
		print(sum_val - 2 + res)

def solver(graph, row, col):
	res = 0
	for r in range(row):
		for c in range(col):
			if graph[r][c] == '0':
				res = 1
				for (_r, _c) in DIRECTIONS:
					if not isValid(r + _r, c + _c, row, col):
						continue
					if graph[r + _r][c + _c] == '0':
						return 2
	return res

def isValid(r, c, row, col):
	if r < 0 or r >= row or c < 0 or (c >= col):
		return False
	return True
main()


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	totalOnes = 0
	ans = 0
	caveFound = False
	maxCave = 0
	inpMat = []
	for row in range(n):
		rowInp = list(map(int, list(input())))
		inpMat.append(rowInp)
		totalOnes += sum(rowInp)
		if not caveFound:
			for col in range(m):
				if rowInp[col] == 0:
					maxCave = 1
					if row != 0 and inpMat[row - 1][col] == 0:
						maxCave = 2
						caveFound = True
					elif col != 0 and inpMat[row][col - 1] == 0:
						maxCave = 2
						caveFound = True
					elif col != 0 and row != 0 and (inpMat[row - 1][col - 1] == 0):
						maxCave = 2
						caveFound = True
					elif row != 0 and col != m - 1 and (inpMat[row - 1][col + 1] == 0):
						maxCave = 2
						caveFound = True
	if caveFound:
		print(totalOnes)
	elif maxCave == 1:
		print(totalOnes - 1)
	else:
		print(totalOnes - 2)


xx = [1, 1, 1, 0, 0, -1, -1, -1]
yy = [-1, 0, 1, 1, -1, -1, 0, 1]
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split(' ')]
	mp = []
	for i in range(n):
		mp.append(input())
	ans = 0
	flag1 = 0
	flag2 = 0
	for i in range(n):
		for j in range(m):
			if mp[i][j] == '1':
				ans += 1
			else:
				if flag2:
					continue
				flag1 = 1
				for k in range(8):
					ii = i + xx[k]
					jj = j + yy[k]
					if ii >= 0 and jj >= 0 and (ii < n) and (jj < m) and (mp[ii][jj] == mp[i][j]):
						flag2 = 1
	if flag2:
		ans = ans
	elif flag1:
		ans = max(ans - 1, 0)
	else:
		ans = max(ans - 2, 0)
	print(ans)


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	cords = [[str(x) for x in input().split()] for i in range(n)]

	def find_all(x, y):
		lis = [[-1, -1], [0, -1], [1, -1], [-1, 0], [1, 0], [-1, 1], [0, 1], [1, 1]]
		lis2 = []
		for (x1, y1) in lis:
			if x1 + int(x) != -1 and x1 + int(x) != m:
				if y1 + int(y) != -1 and y1 + int(y) != n:
					lis2.append([x1, y1])
		for i in lis2:
			if cords[i[1] + y][0][i[0] + x] == '0':
				return True
		return False
	poss = False
	count = 0
	for i in range(n):
		for x in range(m):
			if cords[i][0][x] == '0':
				count += 1
				if poss == False:
					if find_all(x, i):
						poss = True
	if poss:
		print(n * m - count)
	elif count > 0:
		print(n * m - count - 1)
	else:
		print(n * m - 2)


import sys
t = int(input())
for _ in range(t):
	nm = [int(ii) for ii in input().split()]
	(n, m) = (nm[0], nm[1])
	mas = [[2] * (m + 1)] * (n + 1)
	(a, stop) = (0, 0)
	for iii in range(n):
		s = [int(ii) for ii in input()]
		a += sum(s)
		mas[iii] = s + [2]
	if a <= 2:
		print(a)
		continue
	if a == n * m:
		print(a - 2)
		continue
	for i in range(n):
		if stop == 1:
			break
		for j in range(m):
			if mas[i][j] == 0 and (mas[i][j + 1] == 0 or mas[i + 1][j] == 0 or mas[i + 1][j + 1] == 0):
				stop = 1
				break
			if mas[i][j + 1] == 0 and mas[i + 1][j] == 0:
				stop = 1
				break
	if stop == 1:
		print(a)
	else:
		print(a - 1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [input() for i in range(n)]
	q = False
	w = False
	one = 0
	for i in range(n):
		for j in range(m):
			if a[i][j] == '1':
				one += 1
	for i in range(n):
		for j in range(m):
			if a[i][j] == '0':
				zero = 0
				for e in range(max(0, i - 1), min(n - 1, i + 1) + 1):
					for r in range(max(0, j - 1), min(m - 1, j + 1) + 1):
						if a[e][r] == '0':
							zero += 1
				if zero >= 2:
					w = True
					break
				if zero == 1:
					q = True
		if w:
			break
	if w:
		print(one)
	elif q:
		print(one - 1)
	else:
		print(one - 2)


import itertools as it

def spoogly():
	dims = input().split()
	n = int(dims[0])
	m = int(dims[1])
	mat = [0] * n
	for i in range(n):
		mat[i] = [int(x) for x in input()]
	N = sum((sum(mat[i]) for i in range(n)))
	if N == n * m:
		print(N - 2)
	else:
		for (i, j) in it.product(list(range(n - 1)), list(range(m - 1))):
			count = sum((mat[u][v] for u in range(i, i + 2) for v in range(j, j + 2)))
			if count in [0, 1, 2]:
				print(N)
				return
		print(N - 1)
howmanyspoogly = int(input())
for i in range(howmanyspoogly):
	spoogly()


def obok(kordy, ycor):
	for linia in kordy:
		for x in range(len(linia)):
			if linia[x - 1] + 1 == linia[x]:
				return 0
	for linia in range(ycor - 1):
		for x in kordy[linia]:
			temp = (x - 1, x, x + 1)
			for x2 in kordy[linia + 1]:
				if x2 in temp:
					return 0
	return 1
for _ in range(int(input())):
	(y, x) = map(int, input().split())
	(zera, cords) = (0, [])
	for row in range(y):
		rzad = []
		linia = input()
		for i in range(x):
			if linia[i] == '0':
				zera += 1
				rzad += [i]
		cords.append(rzad)
	if zera == 0:
		print(x * y - 2)
	else:
		print(x * y - zera - obok(cords, y))


import sys
t = int(sys.stdin.readline())
for i in range(t):
	(n, m) = map(int, input().split())
	lst = []
	for j in range(n):
		s = input()
		lst.append(s)
	zer = 0
	one = 0
	for x in range(n):
		for y in range(m):
			if lst[x][y] == '0':
				zer += 1
			else:
				one += 1
	if zer == 0:
		print(one - 2)
	else:
		e = 0
		for x in range(n - 1):
			for y in range(m - 1):
				a = lst[x][y]
				b = lst[x + 1][y]
				c = lst[x][y + 1]
				d = lst[x + 1][y + 1]
				lst1 = [a, b, c, d]
				z = lst1.count('0')
				if z >= 2:
					e += 1
					break
		if e > 0:
			print(one)
		else:
			print(one - 1)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	counter = 0
	d = -2
	prev_zeros = [False] * m
	for i in range(n):
		zeros = [False] * m
		s = input()
		for j in range(m):
			if s[j] == '1':
				counter += 1
			else:
				zeros[j] = True
				if j > 0 and zeros[j - 1]:
					d = 0
				elif prev_zeros[j]:
					d = 0
				elif j > 0 and prev_zeros[j - 1]:
					d = 0
				elif j < m - 1 and prev_zeros[j + 1]:
					d = 0
				elif d == -2:
					d = -1
		prev_zeros = zeros
	print(counter + d)


def countone(a, n, m):
	count = 0
	for i in range(n):
		for j in range(m):
			if a[i][j] == 1:
				count += 1
	return count
for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	a = []
	for i in range(n):
		a.append(list(map(int, input())))
	count = countone(a, n, m)
	if count == 0:
		print(0)
	elif count == n * m:
		print(count - 2)
	elif n == m == 2:
		if count == 1:
			print(count)
		else:
			print(2)
	else:
		case = 'no'
		for i in range(n - 1):
			for j in range(m - 1):
				if a[i][j] == a[i][j + 1] == 0 or a[i][j] == a[i + 1][j] == 0 or a[i][j + 1] == a[i + 1][j + 1] == 0 or (a[i + 1][j] == a[i + 1][j + 1] == 0) or (a[i][j] == a[i + 1][j + 1] == 0):
					case = 'a'
					break
				elif a[i + 1][j] == a[i][j + 1] == 0:
					case = 'a'
					break
		if case == 'a':
			print(count)
		else:
			print(count - 1)


def solve():
	x = int(input())
	for _ in range(x):
		[m, n] = list(map(int, input().split()))
		matrix = list()
		for __ in range(m):
			matrix.append(list(map(int, list(input()))))
		ones = 0
		zs = set()
		adj = False
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 1:
					ones += 1
				elif not adj:
					zs.add((i, j))
					moves = [[-1, 0], [1, 0], [0, -1], [0, 1], [1, 1], [-1, -1], [-1, 1], [1, -1]]
					for move in moves:
						if (i + move[0], j + move[1]) in zs:
							adj = True
							break
		if ones == 0:
			print(0)
		elif adj:
			print(ones)
		elif m * n - ones > 0:
			print(ones - 1)
		else:
			print(ones - 2)
solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	before = []
	flag = False
	flag2 = True
	count = 0
	for _ in range(n):
		nxt = []
		left = False
		for (i, num) in enumerate(map(int, list(input().strip()))):
			count += num
			if flag2:
				if num == 0:
					flag = True
					nxt.append(i)
					if i in before or i - 1 in before or i + 1 in before or left:
						check = 0
						flag2 = False
					left = True
				else:
					left = False
		before = nxt
	if flag2:
		if flag:
			check = 1
		else:
			check = 2
	print(count - check)


t = int(input())
for ti in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, list(input()))))
	OneCnt = 0
	for i in a:
		OneCnt += sum(i)
	if OneCnt >= n * m:
		MINU = 2
	else:
		MINU = 1
	for i in range(n):
		for j in range(m):
			if a[i][j] == 0:
				flag = 1
				for di in range(-1, 2):
					for dj in range(-1, 2):
						if (di != 0) | (dj != 0):
							if (i + di < n) & (i + di >= 0) & (j + dj < m) & (j + dj >= 0):
								if a[i + di][j + dj] == 0:
									flag = 0
									break
				if flag == 0:
					MINU = 0
		if MINU == 0:
			break
	print(OneCnt - MINU)


import math
import heapq
import itertools
from typing import List
import bisect
import collections
from collections import defaultdict
from collections import Counter
from collections import deque
time = int(input())
for i in range(time):
	nm = input()
	rc = nm.split(' ')
	row = int(rc[0])
	col = int(rc[1])
	one = 0
	lines = []
	doublezero = False
	for r in range(row):
		line = input()
		lines.append(line)
		cd = Counter(line)
		if '1' in cd:
			one += cd['1']
		if doublezero:
			continue
		if '00' in line:
			doublezero = True
	if doublezero:
		print(one)
	elif one == row * col:
		print(one - 2)
	else:
		zeros = set()
		for r in range(row):
			for c in range(col):
				if lines[r][c] == '0':
					zeros.add((r, c))
					if r - 1 >= 0 and lines[r][c] == lines[r - 1][c]:
						doublezero = True
						break
			if doublezero:
				break
		if doublezero:
			print(one)
		else:
			for (zr, zc) in zeros:
				for (ox, oy) in [(-1, -1), [1, 1], [-1, 1], [1, -1]]:
					(nr, nz) = (zr + ox, zc + oy)
					if (nr, nz) in zeros:
						doublezero = True
						break
				if doublezero:
					break
			if doublezero:
				print(one)
			else:
				print(one - 1)


def isValid(i, j, n, m):
	return i >= 0 and i < n and (j >= 0) and (j < m)
ts = int(input())
for _ in range(ts):
	(n, m) = [int(i) for i in input().split()]
	arr = []
	for _ in range(n):
		x = input()
		l = []
		for a in x:
			l.append(a)
		arr.append(l)
	count = 0
	flag = False
	found = False
	for i in range(n):
		for j in range(m):
			if arr[i][j] == '0':
				found = True
			if arr[i][j] == '1':
				count += 1
			elif flag == False:
				if isValid(i + 1, j, n, m):
					if arr[i + 1][j] == '0':
						flag = True
				if isValid(i, j + 1, n, m):
					if arr[i][j + 1] == '0':
						flag = True
				if isValid(i + 1, j + 1, n, m):
					if arr[i + 1][j + 1] == '0':
						flag = True
				if isValid(i + 1, j - 1, n, m):
					if arr[i + 1][j - 1] == '0':
						flag = True
	if count == 0:
		print(0)
		continue
	if flag:
		print(count)
	elif found:
		print(count - 1)
	else:
		print(count - 2)


n = int(input())
for _ in range(n):
	dim = input().split(' ')
	i = int(dim[0])
	j = int(dim[1])
	matrix = []
	adj = 0
	ones = 0
	bool = False
	for x in range(i):
		matrix += input().split()
		for y in range(j):
			if matrix[x][y] == '0':
				adj = 1
				if y < j - 1 and matrix[x][y + 1] == '0' or (x > 0 and matrix[x - 1][y] == '0') or (y < j - 1 and x > 0 and (matrix[x - 1][y + 1] == '0')) or (x > 0 and y > 0 and (matrix[x - 1][y - 1] == '0')):
					bool = True
			else:
				ones += 1
	if bool:
		print(ones)
	elif adj == 1:
		print(ones - 1)
	else:
		print(ones - 2)


t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	s = []
	o = 0
	v = []
	for i in range(n):
		l = list(input())
		o += l.count('1')
		for j in range(len(l)):
			if l[j] == '0':
				v.append([i, j])
		s.append(l)
	if o == n * m:
		print(n * m - 2)
	elif o == 0:
		print(0)
	else:
		y = 0
		for i in range(len(v)):
			(c, d) = (v[i][0], v[i][1])
			ind = []
			for j in range(3):
				ind.append([c - 1, d - 1 + j])
			ind.append([c, d + 1])
			for j in range(3):
				ind.append([c + 1, d - 1 + j])
			ind.append([c, d - 1])
			for j in ind:
				if (j[0] >= 0 and j[1] >= 0) and (j[0] < n and j[1] < m):
					if s[j[0]][j[1]] == '0':
						y = 1
						break
			if y:
				break
		if y:
			print(o)
		else:
			print(o - 1)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	cnt = 0
	a = []
	for i in range(n):
		s = [*map(int, input())]
		cnt += s.count(1)
		a.append(s)
	c2 = any((True if sum(x[i:i + 2] + y[i:i + 2]) < 3 else False for (x, y) in zip(a, a[1:]) for i in range(m - 1)))
	print(cnt - 2 + c2 + (cnt != m * n))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	m = []
	a = [1]
	b = 0
	for i in range(k):
		a.append(1)
	a.append(1)
	m.append(a)
	a = [1]
	for i in range(n):
		r = input()
		for l in r:
			a.append(int(l))
			if l == '1':
				b += 1
		a.append(1)
		m.append(a)
		a = [1]
	for i in range(k):
		a.append(1)
	a.append(1)
	m.append(a)
	a = [1]
	jeste = True
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if m[i][j] == 0 and 0 in {m[i - 1][j], m[i + 1][j], m[i - 1][j - 1], m[i - 1][j + 1], m[i + 1][j - 1], m[i + 1][j + 1], m[i][j - 1], m[i][j + 1]}:
				jeste = False
				break
	if jeste and b != 0 and (b != n * k):
		b -= 1
	if b == n * k:
		b -= 2
	print(b)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	L = []
	s = 0
	for i in range(n):
		M = list(input())
		s += M.count('1')
		L.append(M)
	if s == 0 or s == 1:
		print(s)
		continue
	if s == n * m:
		print(s - 2)
		continue
	flag1 = 0
	for i in range(n):
		flag2 = 0
		for j in range(1, m):
			if L[i][j] == L[i][j - 1] == '0':
				flag2 = 1
				break
		if flag2:
			flag1 = 1
			break
	for i in range(1, n):
		flag2 = 0
		for j in range(m):
			if L[i][j] == L[i - 1][j] == '0':
				flag2 = 1
				break
		if flag2:
			flag1 = 1
			break
	for i in range(n - 1):
		flag2 = 0
		for j in range(m - 1):
			if L[i][j] == L[i + 1][j + 1] == '0':
				flag2 = 1
				break
		if flag2:
			flag1 = 1
			break
	for i in range(n - 1):
		flag2 = 0
		for j in range(1, m):
			if L[i][j] == L[i + 1][j - 1] == '0':
				flag2 = 1
				break
		if flag2:
			flag1 = 1
			break
	if flag1:
		print(s)
	else:
		print(s - 1)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	c2 = cnt = 0
	a = []
	for i in range(n):
		s = [*map(int, input())]
		cnt += s.count(1)
		a.append(s)
	for (x, y) in zip(a, a[1:]):
		for i in range(m - 1):
			if sum(x[i:i + 2] + y[i:i + 2]) < 3:
				c2 += 1
				break
	if c2:
		print(cnt)
	elif cnt != m * n:
		print(cnt - 1)
	else:
		print(cnt - 2)


for i in range(int(input())):
	(m, n) = map(int, input().split())
	(a, b, c) = ([input() for i in range(m)], 0, 2)
	for i in range(m):
		for j in range(n):
			if a[i][j] == '0':
				c = min(1, c)
				if j + 1 != n and a[i][j + 1] == '0' or (i + 1 != m and a[i + 1][j] == '0') or (j + 1 != n and i + 1 != m and (a[i + 1][j + 1] == '0')) or (j != 0 and i + 1 != m and (a[i + 1][j - 1] == '0')):
					c = 0
		b += a[i].count('1')
	print(b - c)


def maximum_angles_changing(n, m):
	matr = [[0 for _ in range(m)] for _ in range(n)]
	for i in range(n):
		matr[i] = list(map(int, list(input())))
	c_0 = 0
	c_1 = sum([i.count(1) for i in matr])
	cur_c_0 = -10000
	for i in range(n - 1):
		for j in range(m - 1):
			if not matr[i][j]:
				c_0 += 1
			if not matr[i][j + 1]:
				c_0 += 1
			if not matr[i + 1][j]:
				c_0 += 1
			if not matr[i + 1][j + 1]:
				c_0 += 1
			if c_0 > cur_c_0:
				cur_c_0 = c_0
			c_0 = 0
	if cur_c_0 == 0:
		print(c_1 - 2)
	elif cur_c_0 == 1:
		print(c_1 - 1)
	else:
		print(c_1)
t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	maximum_angles_changing(n, m)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = [list(map(int, input())) for i in range(n)]
	c = sum((sum(r) for r in l))
	perfect = False
	for i in range(n - 1):
		for j in range(m - 1):
			s = l[i][j] + l[i + 1][j] + l[i + 1][j + 1] + l[i][j + 1]
			if s <= 2:
				perfect = True
				break
		if perfect:
			break
	if c == 0:
		print(0)
	elif c == n * m:
		print(c - 2)
	else:
		print(c if perfect else c - 1)


for _ in range(int(input())):
	(r, c) = list(map(int, input().split()))
	g = [input() for i in range(r)]
	ct = ''.join(g).count('1')
	res = max(((g[i][j] + g[i + 1][j] + g[i + 1][j + 1] + g[i][j + 1]).count('0') for i in range(r - 1) for j in range(c - 1)))
	print(ct + min(res, 2) - 2)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	o_count = 0
	flag = 0
	st1 = input()
	max_zeros = 0
	for k in range(n - 1):
		st2 = input()
		sh = st1.count('1')
		for j in range(m - 1):
			values = [st1[j], st1[j + 1], st2[j], st2[j + 1]]
			ch = values.count('0')
			max_zeros = max(max_zeros, ch)
		st1 = st2
		o_count += sh
	o_count += st1.count('1')
	if max_zeros >= 2:
		print(o_count)
	elif max_zeros == 1:
		print(o_count - 1)
	else:
		print(o_count - 2)


t = int(input())
for _ in range(t):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	s = []
	for i in range(n):
		ss = input().strip()
		ss = [int(char) for char in ss]
		s.append(ss)
	one_num = sum([sum(row) for row in s])
	hasZero = False if one_num == m * n else True
	has_row2zero = True if min([min([row[i] + row[i + 1] for i in range(m - 1)]) for row in s]) == 0 else False
	has_col2zero = True if min([min([s[i][j] + s[i + 1][j] for i in range(n - 1)]) for j in range(m)]) == 0 else False
	has_xie2zero = False
	for i in range(n - 1):
		for j in range(m - 1):
			if s[i][j] == 0 and s[i + 1][j + 1] == 0:
				has_xie2zero = True
				break
			if s[i + 1][j] == 0 and s[i][j + 1] == 0:
				has_xie2zero = True
				break
	if has_row2zero or has_col2zero or has_xie2zero:
		print(one_num)
	elif hasZero:
		print(one_num - 1)
	else:
		print(one_num - 2)


from itertools import product

def solve(grid, rows, cols):

	def sq_pop(row, col):
		return grid[row][col] + grid[row + 1][col] + grid[row][col + 1] + grid[row + 1][col + 1]
	min_sq_pop = min((sq_pop(row, col) for (row, col) in product(range(rows - 1), range(cols - 1))))
	if min_sq_pop == 4:
		return rows * cols - 2
	elif min_sq_pop == 3:
		return sum((grid[row][col] for (row, col) in product(range(rows), range(cols)))) - 1
	else:
		return sum((grid[row][col] for (row, col) in product(range(rows), range(cols))))
t = int(input())
for _ in range(t):
	(rows, cols) = [int(component) for component in input().split(' ')]
	grid = []
	for row in range(rows):
		grid.append([int(component) for component in input()])
	print(solve(grid, rows, cols))


t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split()]
	matrix = []
	zeros = []
	for j in range(n):
		matrix.append([int(r) for r in list(input())])
		for e in range(m):
			if matrix[-1][e] == 0:
				zeros.append([len(matrix) - 1, e])
	zero = False
	for j in zeros:
		if zeros.count([j[0] + 1, j[1]]) != 0 or zeros.count([j[0], j[1] + 1]) != 0 or zeros.count([j[0] + 1, j[1] + 1]) != 0 or (zeros.count([j[0] - 1, j[1] + 1]) != 0):
			zero = True
			break
	ans = 0
	for e in matrix:
		ans += e.count(1)
	if zero == True:
		print(ans)
	elif len(zeros) >= 1:
		print(ans - 1)
	else:
		print(ans - 2)


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	ar = []
	cnt = 0
	for i in range(n):
		arr = list(map(int, list(input().strip())))
		cnt += arr.count(1)
		ar.append(arr)
	perf = False
	for i in range(n - 1):
		for j in range(m - 1):
			res = ar[i][j] + ar[i + 1][j] + ar[i][j + 1] + ar[i + 1][j + 1]
			if res <= 2:
				perf = True
				break
		if perf:
			break
	if cnt == 0:
		print(0)
	elif cnt == n * m:
		print(cnt - 2)
	elif perf:
		print(cnt)
	else:
		print(cnt - 1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = [list(map(int, input())) for i in range(n)]
	ans = min([max(1, sum(l[i][j:j + 2]) + sum(l[i + 1][j:j + 2]) - 1) for i in range(n - 1) for j in range(m - 1)])
	print(sum((sum(l[i]) for i in range(n))) - ans + 1)


import sys

def read():
	cases = int(sys.stdin.readline())
	for k in range(cases):
		(rows, cols) = [int(num) for num in sys.stdin.readline().split(' ')]
		arr = []
		for r in range(rows):
			arr.append([int(num) for num in sys.stdin.readline().strip()])
		print(solve(arr))

def solve(arr):
	total_ones = 0
	for r in range(len(arr)):
		for c in range(len(arr[0])):
			total_ones += arr[r][c]
	square_sum = float('inf')
	adj_zeroes = False
	for r in range(len(arr) - 1):
		for c in range(len(arr[0]) - 1):
			square_sum = min(square_sum, arr[r][c] + arr[r + 1][c] + arr[r][c + 1] + arr[r + 1][c + 1])
	if square_sum <= 2:
		return total_ones
	elif square_sum == 3:
		return total_ones - 1
	else:
		return total_ones - 2
read()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ones = 0
	prevRow = '1' * m
	dblZ = False
	zero = False
	for r in range(n):
		row = input()
		prevV = 1
		rowLen = len(row)
		for i in range(rowLen):
			v = int(row[i])
			ones += v
			if v == 0:
				if prevRow[i] == row[i] or prevV == v:
					dblZ = True
				if i > 0 and prevRow[i - 1] == row[i]:
					dblZ = True
				elif i < rowLen - 1 and prevRow[i + 1] == row[i]:
					dblZ = True
				zero = True
			prevV = v
		prevRow = row
	if dblZ:
		print(ones)
	elif zero:
		print(ones - 1)
	else:
		print(ones - 2)


for _ in range(int(input())):
	(nco, mde) = map(int, input().split())
	lfine = [list(map(int, input())) for i in range(nco)]
	resans = min([max(1, sum(lfine[i][j:j + 2]) + sum(lfine[i + 1][j:j + 2]) - 1) for i in range(nco - 1) for j in range(mde - 1)])
	print(sum((sum(lfine[i]) for i in range(nco))) - resans + 1)


def checkConnectedZero(a, b, c, d):
	t = [a, b, c, d]
	count = t.count('0')
	if count > 1:
		return True
	return False
t = int(input())
result = []
for i in range(t):
	(n, m) = list(map(int, input().split(' ')))
	ligne = []
	for l in range(n):
		ligne.append(list(input()))
	nbones = 0
	conn = False
	for l in range(n - 1):
		nbones += ligne[l].count('1')
		for c in range(m - 1):
			if checkConnectedZero(ligne[l][c], ligne[l][c + 1], ligne[l + 1][c], ligne[l + 1][c + 1]) == True:
				conn = True
	nbones += ligne[-1].count('1')
	if nbones == 0:
		result.append(0)
	elif nbones == n * m:
		result.append(nbones - 2)
	elif conn == False:
		result.append(nbones - 1)
	else:
		result.append(nbones)
for i in result:
	print(i)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	M = [list(map(int, input())) for i in range(n)]
	k = min([max(1, sum(M[i][j:j + 2]) + sum(M[i + 1][j:j + 2]) - 1) for i in range(n - 1) for j in range(m - 1)])
	print(sum((sum(M[i]) for i in range(n))) - k + 1)


standard_input = '4\n4 3\n101\n111\n011\n110\n3 4\n1110\n0111\n0111\n2 2\n00\n00\n2 2\n11\n11\n'
for _ in range(int(input())):
	(h, w) = map(int, input().split())
	g = [list(map(int, input())) for _ in range(h)]
	c = sum((sum(r) for r in g))
	perfect = False
	for y in range(h - 1):
		for x in range(w - 1):
			s = g[y][x] + g[y][x + 1] + g[y + 1][x] + g[y + 1][x + 1]
			if s <= 2:
				perfect = True
				break
		if perfect:
			break
	if c == 0:
		print(0)
	elif c == h * w:
		print(c - 2)
	else:
		print(c if perfect else c - 1)


t = int(input())
while t != 0:
	(n, m) = map(int, input().split())
	l = [list(map(int, input())) for i in range(n)]
	do = min([max(1, sum(l[i][j:j + 2]) + sum(l[i + 1][j:j + 2]) - 1) for i in range(n - 1) for j in range(m - 1)])
	print(sum((sum(l[i]) for i in range(n))) - do + 1)
	t -= 1


xx = int(input())
for jj in range(xx):
	(n, m) = [int(i) for i in input().split(' ')]
	grid = []
	for i in range(n):
		arr = [int(_) for _ in list(input())]
		grid.append(arr)
	tot = 0
	for i in range(n):
		tot += sum(grid[i])
	p = 4
	for i in range(n - 1):
		for j in range(m - 1):
			p = min(p, grid[i][j] + grid[i + 1][j] + grid[i][j + 1] + grid[i + 1][j + 1])
			if p < 3:
				break
		if p < 3:
			break
	if p < 3:
		print(tot)
	elif p == 3:
		print(tot - 1)
	else:
		print(tot - 2)


R = lambda : [*map(int, input().split())]

def t(a, b):
	return sum(a, b)
for _ in range(int(input())):
	(n, m) = R()
	a = []
	summ = 0
	for _ in range(n):
		b = [*map(int, list(input()))]
		summ += sum(b)
		a.append(b)
	ans = 4
	for i in range(n - 1):
		for j in range(m - 1):
			ans = min(ans, sum(a[i][j:j + 2]) + sum(a[i + 1][j:j + 2]))
			if ans < 3:
				break
	if ans < 3:
		print(summ)
	elif ans == 3:
		print(summ - 1)
	else:
		print(summ - 2)


for _ in range(int(input())):
	s = []
	n = 0
	(r, c) = map(int, input().split())
	for i in range(r):
		s.append(input())
		n += s[i].count('1')
	p = 2
	for i in range(0, r):
		for j in range(0, c):
			if s[i][j] == '0':
				if i > 0 and j > 0 and (p == 2):
					if s[i - 1][j - 1] == '0':
						p = 0
						break
				if i > 0 and p == 2:
					if s[i - 1][j] == '0':
						p = 0
						break
				if i > 0 and j < c - 1 and (p == 2):
					if s[i - 1][j + 1] == '0':
						p = 0
						break
				if j > 0 and p == 2:
					if s[i][j - 1] == '0':
						p = 0
						break
				if j < c - 1 and p == 2:
					if s[i][j + 1] == '0':
						p = 0
						break
				if i < r - 1 and j > 0 and (p == 2):
					if s[i + 1][j - 1] == '0':
						p = 0
						break
				if i < r - 1 and p == 2:
					if s[i + 1][j] == '0':
						p = 0
						break
				if i < r - 1 and j < c - 1 and (p == 2):
					if s[i + 1][j + 1] == '0':
						p = 0
						break
	if n == 0:
		print(0)
	elif n == r * c:
		print(n - 2)
	elif p == 0:
		print(n)
	else:
		print(n - 1)


def zero(l):
	a = 0
	c = False
	s = 0
	for j in range(0, len(l) - 1):
		for k in range(0, len(l[0]) - 1):
			if l[j][k] == 1:
				a = a + 1
			if c == False:
				s = l[j][k] + l[j][k + 1] + l[j + 1][k] + l[j + 1][k + 1]
				if s == 1 or s == 2:
					c = True
			s = 0
	for j in range(0, len(l) - 1):
		if l[j][len(l[0]) - 1] == 1:
			a = a + 1
	for k in range(0, len(l[0])):
		if l[len(l) - 1][k] == 1:
			a = a + 1
	return (a, c)
s = int(input())
for i in range(0, s):
	(n, m) = map(int, input().split())
	l = []
	for j in range(0, n):
		a = input()
		r = []
		for p in range(0, m):
			r.append(int(a[p]))
		l.append(r)
	(x, y) = zero(l)
	if x == n * m:
		print(x - 2)
	elif x == 0:
		print(0)
	elif y:
		print(x)
	else:
		print(x - 1)


def codeforces(arr):
	n = len(arr)
	m = len(arr[0])
	ms = 5
	for i in range(n - 1):
		for j in range(m - 1):
			res = arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1]
			if res:
				ms = min(res, ms)
	if ms == 5:
		return 0
	ans = 0
	for i in range(n):
		for j in range(m):
			ans += arr[i][j]
	if ms == 3:
		return ans - 1
	elif ms == 4:
		return ans - 2
	else:
		return ans
t = int(input())
for test in range(t):
	(n, m) = [int(i) for i in input().split()]
	arr = []
	for i in range(n):
		s = input()
		res = []
		for ind in s:
			res.append(int(ind))
		arr.append(res)
	print(codeforces(arr))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	g = []
	for i in range(n):
		s = input()
		l = []
		for j in range(m):
			l.append(int(s[j]))
		g.append(l)
	ones = 0
	cond = False
	for i in range(n - 1):
		for j in range(m - 1):
			if g[i][j] + g[i + 1][j] + g[i][j + 1] + g[i + 1][j + 1] < 3:
				cond = True
			if g[i][j] == 1:
				ones += 1
	for i in range(n):
		if g[i][-1] == 1:
			ones += 1
	for i in range(m - 1):
		if g[-1][i] == 1:
			ones += 1
	if ones == m * n:
		print(ones - 2)
		continue
	if cond:
		print(ones)
		continue
	print(ones - 1)


import sys

def solve():
	inp = sys.stdin.readline
	(n, m) = map(int, inp().split())
	a = [list(map(int, inp().strip())) for i in range(n)]
	z = 4
	for i in range(1, n):
		for j in range(1, m):
			v = [a[i - 1][j - 1], a[i - 1][j], a[i][j - 1], a[i][j]]
			z = min(z, sum(v) - max(v))
	r = sum((sum(i) for i in a))
	if z == 0:
		print(r)
	else:
		print(r - z + 1)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
import bisect as bi
(t,) = I()
for _ in range(t):
	(n, m) = I()
	grd = []
	an = 0
	for i in range(n):
		grd.append(list(map(int, list(input().strip()))))
		an += grd[-1].count(1)
	mx = 2
	for i in range(n - 1):
		for j in range(m - 1):
			ct = grd[i][j] + grd[i + 1][j] + grd[i][j + 1] + grd[i + 1][j + 1]
			if ct == 3:
				mx = min(1, mx)
			elif ct < 3:
				mx = min(0, mx)
	print(an - mx)


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


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	var = 0
	for j in range(n):
		a = input()
		l.append(a)
		var += a.count('1')
	con = 0
	for j in range(n):
		for k in range(m - 1):
			if l[j][k] == l[j][k + 1] == '0':
				con = 1
				break
	for j in range(m):
		for k in range(n - 1):
			if l[k][j] == l[k + 1][j] == '0':
				con = 1
				break
	i = 0
	for j in range(n - 1):
		for k in range(0, m - 1):
			if l[j][k] == l[j + 1][k + 1] == '0':
				con = 1
				break
	for j in range(n - 1):
		for k in range(0, m - 1):
			if l[j][k + 1] == l[j + 1][k] == '0':
				con = 1
				break
	if n * m == var:
		print(var - 2)
	elif con == 0:
		print(var - 1)
	else:
		print(var)


temp = int(input())
for _ in range(temp):
	(n, m) = map(int, input().split())
	a = [input() for _ in range(n)]
	ans = sum(map(lambda x: x.count('1'), a))
	(x, y) = (4, 0)
	for i in range(n - 1):
		for j in range(m - 1):
			y = a[i][j:j + 2].count('1') + a[i + 1][j:j + 2].count('1')
			x = min(x, y)
	if x == 4:
		ans -= 2
	elif x == 3:
		ans -= 1
	print(ans)


t = int(input())
for e in range(t):
	a = []
	l = list(map(int, input().split()))
	for k in range(l[0]):
		l1 = []
		l2 = input()
		for k in l2:
			l1.append(int(k))
		a.append(l1)

	def chk(i, j):
		if i < 0 or j < 0 or i >= len(a) or (j >= len(a[0])):
			return False
		return a[i][j] == 0
	c = 0
	c2 = 0
	cnt1 = 0
	cnt0 = 0
	for i in range(len(a)):
		for j in range(len(a[0])):
			if a[i][j] == 0:
				cnt0 += 1
				q = chk(i + 1, j) or chk(i - 1, j) or chk(i, j - 1) or chk(i, j + 1) or chk(i - 1, j - 1) or chk(i + 1, j + 1) or chk(i - 1, j + 1) or chk(i + 1, j - 1)
				if q == True:
					c = 1
			else:
				cnt1 += 1
	if c == 1:
		print(cnt1)
	elif cnt0 == 0:
		print(cnt1 - 2)
	else:
		print(cnt1 - 1)


testCase = int(input())
for i in range(testCase):
	info = input().split(' ')
	grid = []
	countOne = 0
	maxxZero = 0
	for j in range(int(info[0])):
		arr = list(input())
		grid.append(arr)
		countOne += arr.count('1')
	for k in range(int(info[0]) - 1):
		for z in range(int(info[1]) - 1):
			count = 0
			count += grid[k][z:z + 2].count('0')
			count += grid[k + 1][z:z + 2].count('0')
			maxxZero = max(maxxZero, count)
	if maxxZero >= 2:
		print(countOne)
	elif maxxZero == 1:
		print(countOne - 1)
	elif maxxZero == 0:
		print(countOne - 2)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lst = [list(map(int, input())) for i in range(n)]
	s = []
	for i in range(n - 1):
		for j in range(m - 1):
			sum_of_4 = sum(lst[i][j:j + 2]) + sum(lst[i + 1][j:j + 2])
			s.append(max(1, sum_of_4 - 1))
	print(sum((sum(lst[i]) for i in range(n))) - min(s) + 1)


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	arr = []
	for i in range(n):
		arr.append([int(x) for x in input()])
	c = 0
	one = 0
	for i in range(n - 1):
		for j in range(m - 1):
			c = max(c, [arr[i][j], arr[i + 1][j], arr[i][j + 1], arr[i + 1][j + 1]].count(0))
	for i in arr:
		for j in i:
			if j == 1:
				one += 1
	if c >= 2:
		print(one)
	elif c == 1:
		print(one - 1)
	elif c == 0:
		print(one - 2)


t = int(input())
for i in range(t):
	shape = input().split()
	shape[0] = int(shape[0])
	shape[1] = int(shape[1])
	arr = []
	for j in range(shape[0]):
		data = input()
		arr.append(data)
	k = 0
	indices = {}
	ones = 0
	zeros = 0
	while k < shape[0] * shape[1]:
		if arr[k // shape[1]][k % shape[1]] == '0':
			indices[k] = '0'
			zeros += 1
		else:
			indices[k] = '1'
			ones += 1
		k = k + 1
	adj = False
	if zeros == 0:
		print(ones - 2)
	else:
		for a in range(len(indices)):
			if indices[a] == '0':
				if a > 0 and indices[a - 1] == '0' and (a % shape[1] > 0) or (a < len(indices) - 1 and indices[a + 1] == '0' and (a % shape[1] < shape[1] - 1)) or (a % shape[1] != 0 and a + shape[1] - 1 < len(indices) and (indices[a + shape[1] - 1] == '0')):
					adj = True
				elif a + shape[1] < len(indices) and indices[a + shape[1]] == '0' or (a % shape[1] != shape[1] - 1 and a + shape[1] + 1 < len(indices) and (indices[a + shape[1] + 1] == '0')):
					adj = True
		if adj == True:
			print(ones)
		else:
			print(ones - 1)


t = int(input())
for tt in range(t):
	(n, m) = map(int, input().split())
	summ = 0
	a = [[0] * m for i in range(n)]
	for i in range(n):
		s = str(input())
		for j in range(m):
			a[i][j] = int(s[j])
			summ += a[i][j]
	minn = 4
	for i in range(n - 1):
		for j in range(m - 1):
			if minn > a[i][j] + a[i + 1][j] + a[i][j + 1] + a[i + 1][j + 1]:
				minn = a[i][j] + a[i + 1][j] + a[i][j + 1] + a[i + 1][j + 1]
	if minn == 0 or minn == 1:
		print(summ)
	else:
		print(summ - (minn - 1) + 1)


tc = int(input())
while tc > 0:
	(n, m) = [int(i) for i in input().split()]
	A = []
	for i in range(n):
		X = [int(i) for i in input()]
		A.append(X)
	no = 0
	mi = 4
	for i in range(m):
		no += A[n - 1][i]
	for i in range(n - 1):
		no += A[i][m - 1]
	for i in range(n - 1):
		for j in range(m - 1):
			no += A[i][j]
			curr = A[i][j] + A[i][j + 1] + A[i + 1][j] + A[i + 1][j + 1]
			mi = min(mi, curr)
	if mi > 2:
		mi -= 2
	else:
		mi = 0
	print(no - mi)
	tc -= 1


t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	l = []
	count = 0
	for i in range(n):
		s = input()
		for j in range(m):
			if s[j] == '1':
				count = count + 1
		l.append(s)
	ans = 0
	for i in range(n - 1):
		for j in range(m - 1):
			ct = 0
			if l[i][j] == '0':
				ct = ct + 1
			if l[i + 1][j] == '0':
				ct = ct + 1
			if l[i][j + 1] == '0':
				ct = ct + 1
			if l[i + 1][j + 1] == '0':
				ct = ct + 1
			ans = max(ans, ct)
	if ans == 4 or ans == 3:
		print(count)
	if ans == 2:
		print(count)
	if ans == 1:
		print(count - 1)
	if ans == 0:
		print(count - 2)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mat = []
	ans = 0
	for _ in range(n):
		s = input()
		ans += s.count('1')
		mat.append(s)
	f = 0
	temp = []
	for i in range(n - 1):
		for j in range(m - 1):
			t1 = int(mat[i][j]) + int(mat[i + 1][j]) + int(mat[i][j + 1]) + int(mat[i + 1][j + 1])
			if t1 <= 2:
				f = 1
	if f:
		print(ans)
	elif ans == n * m:
		print(ans - 2)
	else:
		print(ans - 1)


from bisect import bisect_left
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = False
	e = 0
	a = [[] for x in range(n)]
	for x in range(n):
		s = list(map(int, list(input())))
		e += s.count(1)
		for y in range(m):
			if s[y] == 0:
				a[x].append(y)
	p = []
	for i in a:
		c = -2
		g = 0
		for x in i:
			if x - c == 1:
				ans = True
			c = x
			while g < len(p):
				if p[g] > x:
					if p[g] == x + 1:
						ans = True
					break
				else:
					if abs(p[g] - x) < 2:
						ans = True
					g += 1
		p = i
	if e == n * m:
		print(n * m - 2)
	elif ans:
		print(e)
	else:
		print(e - 1)


T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	mat = []
	(tot, k) = (0, 4)
	for i in range(n):
		X = input()
		row = []
		for x in X:
			row.append(int(x))
		mat.append(row)
		tot += sum(row)
	for i in range(n - 1):
		for j in range(m - 1):
			k = min(k, sum([mat[i][j], mat[i][j + 1], mat[i + 1][j], mat[i + 1][j + 1]]))
	if k == 0 or k == 1:
		print(tot)
	else:
		print(tot - k + 2)