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

You are given a grid with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$). Each cell of this grid contains either water or land. The initial state of the grid is described by strings $S_{1}, S_{2}, \ldots, S_{N}$; for each valid $i$ and $j$, the $j$-th character of $S_{i}$ is '.' if the cell in the $i$-th row and $j$-th column initially contains water or '*' if this cell initially contains land.

A maximal group of connected land cells (by moving between side-adjacent land cells) is called an *island*.

You may perform any number of operations (including zero). In one operation, you should choose one cell of the grid and convert it either to a land cell or to a water cell. Find the smallest number of operations required to maximise the number of islands in the grid.

------  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 valid $i$, the $i$-th of these lines contains a single string $S_{i}$ with length $M$.

------  Output ------
For each test case, print a single line containing one integer ― the smallest number of operations required to maximise the number of islands.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$2 ≤ N, M ≤ 10$
$S_{1}, S_{2}, \ldots, S_{N}$ contain only characters '.' and '*'

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

2 2

..

*.

2 4

*..*

*.*.
----- Sample Output 1 ------ 
1

2
----- explanation 1 ------ 
Example case 1: The largest number of islands is $2$ and it can be achieved by converting one cell from water to land. The resulting grid is

.*
*.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	grid = []
	ans1 = 0
	ans2 = 0
	for i in range(n):
		grid.append(input())
	if not (n % 2 == 1 and m % 2 == 1):
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					cmp = '*'
				else:
					cmp = '.'
				if grid[i][j] != cmp:
					ans1 += 1
				else:
					ans2 += 1
		print(min(ans1, ans2))
	else:
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					cmp = '*'
				else:
					cmp = '.'
				if grid[i][j] != cmp:
					ans1 += 1
		print(ans1)


t = int(input())
while t:
	t -= 1
	q = []
	(n, m) = map(int, input().split())
	for i in range(n):
		s = input()
		q.append(s)
	x = ''
	y = ''
	for i in range(m):
		if i % 2 == 0:
			x += '.'
		else:
			x += '*'
	for i in range(m):
		if i % 2 == 0:
			y += '*'
		else:
			y += '.'
	ans1 = []
	for i in range(n):
		if i % 2 == 0:
			ans1.append(x)
		else:
			ans1.append(y)
	ans2 = []
	for i in range(n):
		if i % 2 == 0:
			ans2.append(y)
		else:
			ans2.append(x)
	ct = 0
	ct1 = 0
	for i in range(n):
		for j in range(m):
			if q[i][j] != ans1[i][j]:
				ct += 1
	for i in range(n):
		for j in range(m):
			if q[i][j] != ans2[i][j]:
				ct1 += 1
	if n * m % 2 == 0:
		print(min(ct, ct1))
	else:
		print(ct1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	t = n * k
	arr = []
	for i in range(n):
		arr.append([str(x) for x in input()])
	ops1 = 0
	ops2 = 0
	for i in range(n):
		for j in range(k):
			if i % 2 == 0:
				if j % 2 == 0 and arr[i][j] == '.':
					ops1 += 1
				elif j % 2 == 1 and arr[i][j] == '*':
					ops1 += 1
			elif j % 2 == 1 and arr[i][j] == '.':
				ops1 += 1
			elif j % 2 == 0 and arr[i][j] == '*':
				ops1 += 1
			if i % 2 == 1:
				if j % 2 == 0 and arr[i][j] == '.':
					ops2 += 1
				elif j % 2 == 1 and arr[i][j] == '*':
					ops2 += 1
			elif j % 2 == 1 and arr[i][j] == '.':
				ops2 += 1
			elif j % 2 == 0 and arr[i][j] == '*':
				ops2 += 1
	if n % 2 == 1 and k % 2 == 1:
		print(ops1)
	else:
		print(min(ops1, ops2))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = []
	for j in range(n):
		x = input()
		l.append(x)
	s = 0
	for k in range(n):
		for z in range(m):
			if (k + z) % 2 == 0:
				if l[k][z] == '.':
					s += 1
			elif l[k][z] == '*':
				s += 1
	if n * m % 2 == 0:
		print(min(s, n * m - s))
	else:
		print(s)


qq = int(input())
for q in range(qq):
	(n, m) = [int(x) for x in input().split()]
	l = []
	for w in range(n):
		p = input()
		l.append(p)
	e = 0
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0:
				if l[i][j] == '.':
					e += 1
			elif l[i][j] == '*':
				e += 1
	if n * m % 2 == 0:
		print(min(e, n * m - e))
	else:
		print(e)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(list(input()))
	(c1, c2) = (0, 0)
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and arr[i][j] == '.':
				c1 = c1 + 1
			if (i + j) % 2 == 1 and arr[i][j] == '*':
				c1 = c1 + 1
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and arr[i][j] == '*':
				c2 = c2 + 1
			if (i + j) % 2 == 1 and arr[i][j] == '.':
				c2 = c2 + 1
	if n * m % 2 == 0:
		print(min(c1, c2))
	else:
		print(c1)


t = int(input())

def match(s, t):
	cnt = 0
	for i in range(len(t)):
		if s[i] != t[i]:
			cnt += 1
	return cnt
for i in range(t):
	(n, m) = map(int, input().split(' '))
	s1 = ''
	s2 = ''
	for j in range(n * m):
		if j % 2 == 0:
			s1 += '.'
			s2 += '*'
		else:
			s1 += '*'
			s2 += '.'
	s = ''
	for j in range(n):
		c = input()
		if j % 2 == 0:
			s += c
		else:
			s += c[::-1]
	if n * m % 2 == 0:
		a1 = match(s, s1)
		a2 = match(s, s2)
		ans = min(a1, a2)
		print(ans)
	else:
		ans = match(s, s2)
		print(ans)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(input())
	if n * m % 2 == 0:
		ans1 = 0
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					if arr[i][j] != '*':
						ans1 = ans1 + 1
				elif arr[i][j] != '.':
					ans1 = ans1 + 1
		ans2 = 0
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					if arr[i][j] != '.':
						ans2 = ans2 + 1
				elif arr[i][j] != '*':
					ans2 = ans2 + 1
		print(min(ans1, ans2))
	else:
		ans1 = 0
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					if arr[i][j] != '*':
						ans1 = ans1 + 1
				elif arr[i][j] != '.':
					ans1 = ans1 + 1
		print(ans1)


def string_start(lst, m, c, d):
	o = ''
	for i in range(m):
		if i % 2 == 0:
			o += '.'
			if lst[d][i] != '.':
				c += 1
		else:
			o += '*'
			if lst[d][i] != '*':
				c += 1
	lst[d] = o
	return c

def string_start_1(lst, m, c, d):
	o = ''
	for i in range(m):
		if i % 2 == 0:
			o += '*'
			if lst[d][i] != '*':
				c += 1
		else:
			o += '.'
			if lst[d][i] != '.':
				c += 1
	lst[d] = o
	return c

def string_changes(lst, m, c):
	if len(lst) == 1:
		return c
	else:
		o = ''
		for i in range(m):
			if lst[-1][i] == lst[-2][i]:
				c += 1
				if lst[-2][i] == '*':
					o += '.'
				else:
					o += '*'
			else:
				o += lst[-2][i]
		lst[-2] = o
		lst.pop(len(lst) - 1)
		return string_changes(lst, m, c)

def string_changes_front(lst, m, c):
	if len(lst) == 1:
		return c
	else:
		o = ''
		for i in range(m):
			if lst[0][i] == lst[1][i]:
				c += 1
				if lst[1][i] == '*':
					o += '.'
				else:
					o += '*'
			else:
				o += lst[1][i]
		lst[1] = o
		lst.pop(0)
		return string_changes_front(lst, m, c)
for i in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	lst = []
	lst1 = []
	arr1 = []
	for j in range(n):
		s = input()
		lst.append(s)
		arr.append(s)
		lst1.append(s)
		arr1.append(s)
	(c_l, cl) = (0, 0)
	(c_r, cr) = (0, 0)
	if n * m % 2 != 0:
		cl += string_start_1(lst1, m, 0, -1)
		cl += string_changes(lst1, m, 0)
		cr += string_start_1(arr1, m, 0, 0)
		cr += string_changes_front(arr1, m, 0)
		print(min(cl, cr))
	else:
		c_l += string_start(lst, m, 0, -1)
		c_l += string_changes(lst, m, 0)
		cl += string_start_1(lst1, m, 0, -1)
		cl += string_changes(lst1, m, 0)
		c_r += string_start(arr, m, 0, 0)
		c_r += string_changes_front(arr, m, 0)
		cr += string_start_1(arr1, m, 0, 0)
		cr += string_changes_front(arr1, m, 0)
		print(min(cl, cr, c_l, c_r))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for _ in range(n):
		a.append(list(input()))
	a1 = 0
	a2 = 0
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and a[i][j] == '.':
				a1 += 1
			if (i + j) % 2 == 1 and a[i][j] == '*':
				a1 += 1
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and a[i][j] == '*':
				a2 += 1
			if (i + j) % 2 == 1 and a[i][j] == '.':
				a2 += 1
	if n * m % 2 == 0:
		print(min(a1, a2))
	else:
		print(a1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = []
	for _ in range(n):
		d.append(list(input()))
	d1 = 0
	d2 = 0
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and d[i][j] == '.':
				d1 += 1
			if (i + j) % 2 == 1 and d[i][j] == '*':
				d1 += 1
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and d[i][j] == '*':
				d2 += 1
			if (i + j) % 2 == 1 and d[i][j] == '.':
				d2 += 1
	if n * m % 2 == 0:
		print(min(d1, d2))
	else:
		print(d1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [[0 for _ in range(m)] for i in range(n)]
	sum = 0
	for i in range(n):
		x = input()
		for j in range(m):
			if x[j] == '*':
				a[i][j] = 1
			sum += abs(a[i][j] - (1 - (i + j) % 2))
	if n * m % 2 == 0:
		print(min(sum, m * n - sum))
	else:
		print(sum)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	grid = [list(map(str, input())) for i in range(N)]
	d = 0
	for i in range(N):
		for j in range(M):
			if grid[i][j] == '*':
				grid[i][j] = 1
			else:
				grid[i][j] = 0
			if grid[i][j] != (i + j + 1) % 2:
				d += 1
	if N * M % 2 == 0:
		print(min(M * N - d, d))
	else:
		print(d)


T = int(input())
for i in range(T):
	(n, m) = map(int, input().split())
	if n * m % 2 == 0:
		x1 = 0
		x2 = 0
		for i in range(n):
			a = input()
			for j in range(m):
				if (i + j) % 2 == 0:
					if a[j] == '.':
						x1 += 1
					else:
						x2 += 1
				elif a[j] == '*':
					x1 += 1
				else:
					x2 += 1
		print(min(x1, x2))
	else:
		c = 0
		for i in range(n):
			a = input()
			for j in range(m):
				if (i + j) % 2 == 0:
					if a[j] == '.':
						c += 1
				elif a[j] == '*':
					c += 1
		print(c)


def mgc():
	ops1 = 0
	for i in range(n):
		for j in range(m):
			if i % 2 == 0:
				if j % 2 == 0 and arr[i][j] == '.':
					ops1 += 1
				elif j % 2 == 1 and arr[i][j] == '*':
					ops1 += 1
			elif j % 2 == 1 and arr[i][j] == '.':
				ops1 += 1
			elif j % 2 == 0 and arr[i][j] == '*':
				ops1 += 1
	ops2 = 0
	for i in range(n):
		for j in range(m):
			if i % 2 == 1:
				if j % 2 == 0 and arr[i][j] == '.':
					ops2 += 1
				elif j % 2 == 1 and arr[i][j] == '*':
					ops2 += 1
			elif j % 2 == 1 and arr[i][j] == '.':
				ops2 += 1
			elif j % 2 == 0 and arr[i][j] == '*':
				ops2 += 1
	if n * m % 2 == 0:
		return min(ops2, ops1)
	else:
		return ops1
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(input())
	print(mgc())


def solve2(n, m, li, c1, c2):
	for i in range(n):
		for j in range(m):
			if i % 2 == 0:
				if j % 2 == 0:
					if li[i][j] == '.':
						c1 += 1
				elif li[i][j] == '*':
					c1 += 1
			elif j % 2 == 0:
				if li[i][j] == '*':
					c1 += 1
			elif li[i][j] == '.':
				c1 += 1
	return c1

def solve1(n, m, li, c1, c2):
	for i in range(n):
		for j in range(m):
			if i % 2 == 0:
				if j % 2 == 0:
					if li[i][j] == '.':
						c1 += 1
				elif li[i][j] == '*':
					c1 += 1
			elif j % 2 == 0:
				if li[i][j] == '*':
					c1 += 1
			elif li[i][j] == '.':
				c1 += 1
			if i % 2 == 1:
				if j % 2 == 0:
					if li[i][j] == '.':
						c2 += 1
				elif li[i][j] == '*':
					c2 += 1
			elif j % 2 == 0:
				if li[i][j] == '*':
					c2 += 1
			elif li[i][j] == '.':
				c2 += 1
	return min(c1, c2)
for testcase in range(int(input())):
	arr = [int(x) for x in input().split()]
	(n, m) = (arr[0], arr[1])
	li = []
	for i in range(n):
		s = list(input())
		li.append(s)
	(c1, c2) = (0, 0)
	if n % 2 == 0 or m % 2 == 0:
		print(solve1(n, m, li, c1, c2))
	else:
		print(solve2(n, m, li, c1, c2))


def test(n, m):
	a = '*'
	b = '.'
	s1 = ''
	s2 = ''
	for i in range(m):
		if i % 2 == 0:
			s1 += a
			s2 += b
		else:
			s1 += b
			s2 += a
	ls1 = []
	ls2 = []
	for i in range(n):
		if i % 2 == 0:
			ls1.append(s1)
			ls2.append(s2)
		else:
			ls1.append(s2)
			ls2.append(s1)
	a = sum((i.count('*') for i in ls1))
	b = sum((i.count('*') for i in ls2))
	if a == b:
		return (ls1, ls2)
	elif a > b:
		return (ls1, ls1)
	else:
		return (ls2, ls2)

def diff(ls1, ls2):
	count = 0
	for i in range(len(ls1)):
		s1 = ls1[i]
		s2 = ls2[i]
		for j in range(len(s1)):
			if s1[j] != s2[j]:
				count += 1
	return count
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	(ls1, ls2) = test(n, m)
	ls3 = [input() for i in range(n)]
	print(min(diff(ls1, ls3), diff(ls2, ls3)))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lis = []
	for _ in range(n):
		lis.append([x for x in input()])
	count1 = 0
	for i in range(n):
		if i % 2 == 0:
			flag = 0
		else:
			flag = 1
		for j in range(m):
			if flag == 0:
				if lis[i][j] == '.':
					count1 += 1
				flag = 1
			else:
				if lis[i][j] == '*':
					count1 += 1
				flag = 0
	count2 = 0
	for i in range(n):
		if i % 2 == 0:
			flag = 0
		else:
			flag = 1
		for j in range(m):
			if flag == 0:
				if lis[i][j] == '*':
					count2 += 1
				flag = 1
			else:
				if lis[i][j] == '.':
					count2 += 1
				flag = 0
	if n * m % 2 == 1:
		print(count1)
	else:
		print(min(count1, count2))


def count(s, n, m):
	cur = 0
	ans = 0
	for i in range(n):
		cur = i % 2
		for j in range(m):
			if cur % 2 == 0:
				if '*' != s[i][j]:
					ans += 1
			elif '.' != s[i][j]:
				ans += 1
			cur += 1
	if n * m % 2 == 1:
		return ans
	ans2 = 0
	cur = 0
	for i in range(n):
		cur = i % 2
		for j in range(m):
			if cur % 2 == 0:
				if '.' != s[i][j]:
					ans2 += 1
			elif '*' != s[i][j]:
				ans2 += 1
			cur += 1
		cur = 0
	return min(ans2, ans)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = [input() for _ in range(n)]
	print(count(s, n, m))


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	s = []
	cs = [0] * 2
	cd = [0] * 2
	for _ in range(a):
		s.append(str(input()))
	for i in range(a):
		for j in range(b):
			if s[i][j] == '*':
				cs[(i + j) % 2] += 1
			else:
				cd[(i + j) % 2] += 1
	t = a * b // 2
	if a % 2 == 0 or b % 2 == 0:
		ans1 = abs(cs[0] - t) + abs(t - cd[1])
		ans2 = abs(cs[1] - t) + abs(t - cd[0])
		print(min(ans1, ans2))
	else:
		print(abs(cs[0] - (t + 1)) + abs(cd[1] - t))


def graph_traversal(dp):
	tmp = 0
	for i in range(n):
		for j in range(1, m):
			if dp[i][j - 1] == '*':
				dp[i][j] = '.'
			else:
				dp[i][j] = '*'
			if dp[i][j] != grid[i][j]:
				tmp += 1
		if dp[i][0] != grid[i][0]:
			tmp += 1
		if i < n - 1:
			if dp[i][0] == '*':
				dp[i + 1][0] = '.'
			else:
				dp[i + 1][0] = '*'
	return tmp

def calculate(n, m, grid):
	ans = float('inf')
	dp = [[0] * m for _ in range(n)]
	dp[0][0] = '*'
	ans = min(graph_traversal(dp), ans)
	if n % 2 == 0 or m % 2 == 0:
		dp[0][0] = '.'
		ans = min(graph_traversal(dp), ans)
	return ans
T = int(input())
while T:
	(n, m) = map(int, input().split())
	grid = []
	for _ in range(n):
		grid.append(input())
	print(calculate(n, m, grid))
	T -= 1


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		temp = input()
		l.append(temp)
	ans1 = 0
	ans2 = 0
	for i in range(len(l)):
		s = l[i]
		for j in range(len(s)):
			if (i + j) % 2 == 0 and s[j] == '.':
				ans1 = ans1 + 1
			elif (i + j) % 2 == 1 and s[j] == '*':
				ans1 = ans1 + 1
	for i in range(len(l)):
		s = l[i]
		for j in range(len(s)):
			if (i + j) % 2 == 0 and s[j] == '*':
				ans2 = ans2 + 1
			elif (i + j) % 2 == 1 and s[j] == '.':
				ans2 = ans2 + 1
	if n * m % 2 == 0:
		print(min(ans1, ans2))
	elif n * m % 2 == 1:
		print(ans1)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		temp = input()
		l.append(temp)
	if n * m % 2 == 0:
		ans1 = 0
		for i in range(n):
			for j in range(m):
				if i % 2 == 0 and j % 2 == 0 and (l[i][j] == '.') or (i % 2 != 0 and j % 2 == 0 and (l[i][j] == '*')) or (i % 2 == 0 and j % 2 != 0 and (l[i][j] == '*')) or (i % 2 != 0 and j % 2 != 0 and (l[i][j] == '.')):
					ans1 += 1
		ans2 = 0
		for i in range(n):
			for j in range(m):
				if i % 2 == 0 and j % 2 == 0 and (l[i][j] == '*') or (i % 2 != 0 and j % 2 == 0 and (l[i][j] == '.')) or (i % 2 == 0 and j % 2 != 0 and (l[i][j] == '.')) or (i % 2 != 0 and j % 2 != 0 and (l[i][j] == '*')):
					ans2 += 1
		print(min(ans1, ans2))
	else:
		ans1 = 0
		for i in range(n):
			for j in range(m):
				if i % 2 == 0 and j % 2 == 0 and (l[i][j] == '.') or (i % 2 != 0 and j % 2 == 0 and (l[i][j] == '*')) or (i % 2 == 0 and j % 2 != 0 and (l[i][j] == '*')) or (i % 2 != 0 and j % 2 != 0 and (l[i][j] == '.')):
					ans1 += 1
		print(ans1)


def numchanged(grid, N, M, parity):
	count = 0
	for i in range(N):
		for j in range(M):
			if (i + j) % 2 == parity:
				if grid[i][j] != '*':
					count += 1
			elif grid[i][j] != '.':
				count += 1
	return count
t = int(input())
for _ in range(t):
	(N, M) = map(int, input().split())
	grid = []
	for i in range(N):
		grid.append(input())
	if N % 2 == 1 and M % 2 == 1:
		print(numchanged(grid, N, M, 0))
		continue
	else:
		first = numchanged(grid, N, M, 0)
		second = numchanged(grid, N, M, 1)
		print(min(first, second))


tc = int(input())
for t in range(0, tc):
	(N, M) = input().split()
	(N, M) = (int(N), int(M))
	inparr = []
	sol1 = []
	sol2 = []
	for n in range(0, N):
		ia = []
		s1a = []
		s2a = []
		for m in range(0, M):
			ia.append('-1')
			if (n + m) % 2 == 0:
				s1a.append('*')
				s2a.append('.')
			else:
				s1a.append('.')
				s2a.append('*')
		inparr.append(ia)
		sol1.append(s1a)
		sol2.append(s2a)
	ans1 = 0
	ans2 = 0
	for s in range(0, N):
		S = input()
		for l in range(0, len(S)):
			temp = S[l]
			if sol1[s][l] != temp:
				ans1 += 1
			if sol2[s][l] != temp:
				ans2 += 1
			inparr[s][l] = temp
	if N % 2 != 0 and M % 2 != 0:
		print(ans1)
	elif ans1 > ans2:
		print(ans2)
	else:
		print(ans1)


t = int(input())
arr1 = [['*', '.', '*', '.', '*', '.', '*', '.', '*', '.', '*'], ['.', '*', '.', '*', '.', '*', '.', '*', '.', '*', '.']]
arr2 = [['.', '*', '.', '*', '.', '*', '.', '*', '.', '*', '.'], ['*', '.', '*', '.', '*', '.', '*', '.', '*', '.', '*']]
for i in range(t):
	(n, m) = map(int, input().split(' '))
	count1 = 0
	count2 = 0
	if n % 2 == 0 or m % 2 == 0:
		for j in range(n):
			temp = input()
			arrInput = list(temp)
			for k in range(m):
				var = int(j % 2)
				if not arr1[var][k] == arrInput[k]:
					count1 += 1
				if not arr2[var][k] == arrInput[k]:
					count2 += 1
		print(min(count1, count2))
	else:
		for j in range(n):
			temp = input()
			arrInput = list(temp)
			for k in range(m):
				var = int(j % 2)
				if arr1[var][k] != arrInput[k]:
					count1 += 1
		print(count1)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		temp = input()
		arr.append(list(temp))
	arr1 = [['.' for i in range(m)] for j in range(n)]
	arr2 = [['*' for i in range(m)] for j in range(n)]
	flag = True
	for i in range(0, n, 1):
		if flag:
			for j in range(0, m, 2):
				arr1[i][j] = '*'
				arr2[i][j] = '.'
			flag = False
		else:
			for j in range(1, m, 2):
				arr1[i][j] = '*'
				arr2[i][j] = '.'
			flag = True
	cnt1 = 0
	cnt2 = 0
	if n % 2 == 0 or m % 2 == 0:
		for i in range(n):
			for j in range(m):
				if arr[i][j] != arr1[i][j]:
					cnt1 += 1
				if arr[i][j] != arr2[i][j]:
					cnt2 += 1
		print(min(cnt1, cnt2))
	else:
		for i in range(n):
			for j in range(m):
				if arr[i][j] != arr1[i][j]:
					cnt1 += 1
		print(cnt1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m % 2 == 0 or n % 2 == 0:
		(c1, c2) = (0, 0)
		for i in range(n):
			s = input()
			for j in range(m):
				if i % 2 == 0 and j % 2 == 0 or (i % 2 == 1 and j % 2 == 1):
					if s[j] == '.':
						c1 += 1
					else:
						c2 += 1
				elif s[j] == '*':
					c1 += 1
				else:
					c2 += 1
		print(min(c1, c2))
	else:
		c = 0
		for i in range(n):
			s = input()
			for j in range(m):
				if i % 2 == 0 and j % 2 == 0 or (i % 2 == 1 and j % 2 == 1):
					if s[j] == '.':
						c += 1
				elif s[j] == '*':
					c += 1
		print(c)


def co(li):
	count = 0
	for i in range(len(li)):
		for j in range(len(li[i])):
			if li[i][j] == '*':
				count += 1
	return count
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	li = []
	for i in range(n):
		s = input()
		li.append(s)
	li1 = []
	li2 = []
	(s1, s2) = ('', '')
	for i in range(m):
		if i & 1 == 0:
			s1 += '*'
			s2 += '.'
		else:
			s1 += '.'
			s2 += '*'
	for i in range(n):
		if i & 1 == 0:
			li1.append(s1)
			li2.append(s2)
		else:
			li1.append(s2)
			li2.append(s1)
	(c1, c2) = (0, 0)
	(star1, star2) = (co(li1), co(li2))
	if star1 > star2:
		ans = 0
		for i in range(n):
			for j in range(m):
				if li[i][j] != li1[i][j]:
					ans += 1
		print(ans)
	elif star2 > star1:
		ans = 0
		for i in range(n):
			for j in range(m):
				if li[i][j] != li2[i][j]:
					ans += 1
		print(ans)
	else:
		for i in range(n):
			for j in range(m):
				if li[i][j] != li1[i][j]:
					c1 += 1
				if li[i][j] != li2[i][j]:
					c2 += 1
		print(min(c1, c2))


for _ in range(int(input())):
	s = []
	(n, m) = map(int, input().split())
	for i in range(n):
		s.append(input())
	c = 0
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and s[i][j] != '*' or ((i + j) % 2 == 1 and s[i][j] != '.'):
				c += 1
	ans = c
	if n * m % 2 == 0:
		c = 0
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0 and s[i][j] != '.' or ((i + j) % 2 == 1 and s[i][j] != '*'):
					c += 1
	print(min(ans, c))


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	li = []
	for i in range(r):
		li.append(list(input()))
	ch1 = 0
	ch2 = 0
	if r % 2 == 0 or c % 2 == 0:
		for i in range(r):
			for j in range(c):
				if (i + j) % 2 == 0:
					if li[i][j] == '.':
						ch1 += 1
					else:
						ch2 += 1
				elif li[i][j] == '*':
					ch1 += 1
				else:
					ch2 += 1
		print(min(ch1, ch2))
	else:
		for i in range(r):
			for j in range(c):
				if (i + j) % 2 == 0:
					if li[i][j] == '.':
						ch1 += 1
				elif li[i][j] == '*':
					ch1 += 1
		print(ch1)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		u = list(input())
		l.append(u)
	(ans1, ans2) = (0, 0)
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and l[i][j] == '.':
				ans1 += 1
			elif (i + j) % 2 == 1 and l[i][j] == '*':
				ans1 += 1
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and l[i][j] == '*':
				ans2 += 1
			elif (i + j) % 2 == 1 and l[i][j] == '.':
				ans2 += 1
	if n * m % 2 == 0:
		print(min(ans1, ans2))
	else:
		print(ans1)


for fgh in range(int(input())):
	arr = []
	(n, m) = map(int, input().split())
	for i in range(n):
		arr.append(list(input()))
	c1 = 0
	c2 = 0
	count = 0
	for i in range(len(arr)):
		if i % 2 == 0:
			for j in range(1, len(arr[i]), 2):
				if arr[i][j] == '*':
					count += 1
		else:
			for j in range(0, len(arr[i]), 2):
				if arr[i][j] == '*':
					count += 1
	c1 = count
	count = 0
	for i in range(len(arr)):
		if i % 2 != 0:
			for j in range(1, len(arr[i]), 2):
				if arr[i][j] == '*':
					count += 1
		else:
			for j in range(0, len(arr[i]), 2):
				if arr[i][j] == '*':
					count += 1
	c2 = count
	if n * m % 2 == 0:
		req = n * m / 2
		print(min(int(req - c1 + c2), int(req - c2 + c1)))
	else:
		req = n * m // 2 + 1
		print(int(req - c2 + c1))


def fn(N, M, L):
	array = [['*', '.', '*', '.', '*', '.', '*', '.', '*', '.'], ['.', '*', '.', '*', '.', '*', '.', '*', '.', '*']]
	if N * M % 2 == 0:
		count1 = 0
		count2 = 0
		for i in range(N):
			if i % 2 == 0:
				for j in range(M):
					if L[i][j] != array[0][j]:
						count1 += 1
			else:
				for j in range(M):
					if L[i][j] != array[1][j]:
						count1 += 1
		for i in range(N):
			if i % 2 == 0:
				for j in range(M):
					if L[i][j] != array[1][j]:
						count2 += 1
			else:
				for j in range(M):
					if L[i][j] != array[0][j]:
						count2 += 1
		return min(count1, count2)
	else:
		count = 0
		for i in range(N):
			if i % 2 == 0:
				for j in range(M):
					if L[i][j] != array[0][j]:
						count += 1
			else:
				for j in range(M):
					if L[i][j] != array[1][j]:
						count += 1
		return count
t = int(input())
for i in range(t):
	(N, M) = map(int, input().strip().split())
	List = []
	for j in range(N):
		List.append(list(input()))
	print(fn(N, M, List))


import sys
import math
input = sys.stdin.readline
T = int(input())
for _ in range(T):

	def solve(n, m, arr):
		stars = [0, 0]
		dots = [0, 0]
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					if arr[i][j] == '*':
						stars[0] += 1
					else:
						dots[0] += 1
				elif arr[i][j] == '*':
					stars[1] += 1
				else:
					dots[1] += 1
		half = n * m // 2
		if n * m % 2 == 1:
			ans = dots[0] + stars[1]
		else:
			ans1 = abs(half - dots[0]) + abs(half - stars[1])
			ans2 = abs(half - dots[1]) + abs(half - stars[0])
			ans = min(ans1, ans2)
		return ans
	(n, m) = map(int, input().split())
	arr = ['' for _ in range(n)]
	for i in range(n):
		arr[i] = input()
	print(solve(n, m, arr))


t = int(input())
for i in range(t):
	ar = []
	[n, m] = list(map(int, input().split()))
	for j in range(0, n):
		x = list(map(str, input()))
		ar.append(x)
	c = 0
	d = 0
	for j in range(n):
		for k in range(m):
			if (j + k) % 2 == 0:
				if ar[j][k] == '.':
					c += 1
				else:
					d += 1
			elif ar[j][k] == '*':
				c += 1
			else:
				d += 1
	if n % 2 != 0 and m % 2 != 0:
		print(c)
	else:
		print(min(c, d))


testcases = int(input())
for testcase in range(testcases):
	temparr = input()
	temparr = temparr.split()
	r = int(temparr[0])
	c = int(temparr[1])
	dp = []
	temparr = []
	for i in range(r):
		tt = []
		tempstr = input()
		for j in tempstr:
			if j == '*':
				tt.append(1)
			else:
				tt.append(0)
		dp.append(tt[:])
	oddeven = 0
	evenodd = 0
	flag = 0
	correct = 0
	for i in range(r):
		if i & 1:
			flag = 0
		else:
			flag = 1
		for j in range(c):
			if flag == 0 and dp[i][j] != 0:
				evenodd += 1
				flag = 1
			elif flag == 1 and dp[i][j] != 1:
				evenodd += 1
				flag = 0
			elif flag == 0:
				correct += 1
				flag = 1
			elif flag == 1:
				correct += 1
				flag = 0
	ans = min(correct, evenodd)
	if r & 1 and c & 1:
		print(evenodd)
	else:
		print(ans)


def isValid(x, y):
	if x >= 0 and x < n and (y >= 0) and (y < m):
		return True
	return False
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	grid = [list(input()) for i in range(n)]
	(s1, s2) = (0, 0)
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0:
				if grid[i][j] == '.':
					s1 += 1
				elif n * m % 2 == 0:
					s2 += 1
			elif grid[i][j] == '*':
				s1 += 1
			elif n * m % 2 == 0:
				s2 += 1
	if n * m % 2 != 0:
		s2 = 2 ** 30
	print(min(s1, s2))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	k = '*.' * (b // 2)
	p = '.*' * (b // 2)
	if b % 2 != 0:
		k += '*'
		p += '.'
	t = 0
	v = 0
	fg = 0
	kg = 0
	for i in range(a):
		r = input()
		for j in range(b):
			if fg == 0:
				if r[j] != p[j]:
					v += 1
			elif r[j] != k[j]:
				v += 1
			if kg == 0:
				if r[j] != k[j]:
					t += 1
			elif r[j] != p[j]:
				t += 1
		fg = (fg + 1) % 2
		kg = (kg + 1) % 2
	if a % 2 == 1 and b % 2 == 1:
		print(t)
		continue
	print(min(v, t))


t = int(input())
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	s = ''
	for i in range(n):
		if i % 2 != 0:
			s += input()
		else:
			ss = input()
			s += ss[::-1]
	i = 0
	ss = ''
	ss1 = ''
	while i <= n * m:
		ss += '*.'
		ss1 += '.*'
		i += 1
	if i != n * m:
		ss += '*'
		ss1 += '.'
	ans1 = 0
	ans2 = 0
	j = 0
	for i in s:
		if i != ss[j]:
			ans1 += 1
		if i != ss1[j]:
			ans2 += 1
		j += 1
	if n * m % 2 == 0:
		print(min(ans1, ans2))
	else:
		print(ans1)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split(' '))
	fulls = []
	count1 = 0
	count2 = 0
	loji1 = 0
	loji2 = 0
	for i in range(n):
		fulls.append(list(input()))
	for i in range(n):
		for j in range(m):
			if (i + 1) % 2 == 1:
				if (j + 1) % 2 == 1:
					if fulls[i][j] != '*':
						count1 += 1
					loji1 += 1
				elif fulls[i][j] != '.':
					count1 += 1
			if (i + 1) % 2 == 0:
				if (j + 1) % 2 == 0:
					if fulls[i][j] != '*':
						count1 += 1
					loji1 += 1
				elif fulls[i][j] != '.':
					count1 += 1
	for i in range(n):
		for j in range(m):
			if (i + 1) % 2 == 1:
				if (j + 1) % 2 == 1:
					if fulls[i][j] != '.':
						count2 += 1
				else:
					if fulls[i][j] != '*':
						count2 += 1
					loji2 += 1
			if (i + 1) % 2 == 0:
				if (j + 1) % 2 == 0:
					if fulls[i][j] != '.':
						count2 += 1
				else:
					if fulls[i][j] != '*':
						count2 += 1
					loji2 += 1
	if loji2 > loji1:
		print(count2)
	elif loji1 > loji2:
		print(count1)
	else:
		print(min(count1, count2))


from sys import stdin, stdout, setrecursionlimit
import heapq
from math import gcd, ceil, sqrt
from collections import Counter, deque
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007

def getMat(n, m, init):
	a = b = init
	mat = []
	for i in range(n):
		b = a
		cur = []
		for j in range(m):
			cur.append('*' if b == 0 else '.')
			b ^= 1
		a ^= 1
		mat.append(cur)
	return mat

def compare(mat1, mat2):
	res = 0
	for i in range(len(mat1)):
		for j in range(len(mat1[0])):
			if mat1[i][j] != mat2[i][j]:
				res += 1
	return res

def count(mat):
	cnt = 0
	for i in range(len(mat)):
		for j in range(len(mat[0])):
			if mat[i][j] == '*':
				cnt += 1
	return cnt
tc = ii1()
for _ in range(tc):
	(n, m) = iia()
	mat = []
	for i in range(n):
		mat.append(list(is1()))
	mat1 = getMat(n, m, 0)
	mat2 = getMat(n, m, 1)
	(cnt1, cnt2) = (count(mat1), count(mat2))
	if cnt1 == cnt2:
		res = compare(mat1, mat)
		res = min(res, compare(mat2, mat))
	elif cnt1 > cnt2:
		res = compare(mat1, mat)
	else:
		res = compare(mat2, mat)
	print(res)


L1 = []
L2 = []
for i in range(10):
	l1 = []
	l2 = []
	for j in range(10):
		if (i + j) % 2 == 0:
			l1.append('*')
			l2.append('.')
		else:
			l1.append('.')
			l2.append('*')
	L1.append(l1)
	L2.append(l2)
t = int(input())
for i in range(t):
	(N, M) = list(map(int, input().split()))
	NM = []
	for i in range(N):
		nm = list(input())
		NM.append(nm)
	c1 = 0
	c2 = 0
	for i in range(N):
		for j in range(M):
			if NM[i][j] != L1[i][j]:
				c1 += 1
			if NM[i][j] != L2[i][j]:
				c2 += 1
	if N * M % 2 != 0:
		print(c1)
	elif c2 < c1:
		print(c2)
	else:
		print(c1)


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	tisl = math.ceil(n * m / 2)
	mapls = []
	f1 = []
	f2 = []
	lcount = 0
	for i in range(n):
		ss = input()
		mapls.append(ss)
		if not i % 2:
			f1s = '*.' * (int(m) // 2)
			if m % 2:
				f1s += '*'
			f2s = '.*' * (int(m) // 2)
			if m % 2:
				f2s += '.'
		else:
			f1s = '.*' * (int(m) // 2)
			if m % 2:
				f1s += '.'
			f2s = '*.' * (int(m) // 2)
			if m % 2:
				f2s += '*'
		f1.append(f1s)
		f2.append(f2s)
	f1c = 0
	f2c = 0
	for i in range(n):
		for j in range(m):
			if mapls[i][j] != f1[i][j]:
				f1c += 1
			if mapls[i][j] != f2[i][j]:
				f2c += 1
	if n % 2 and m % 2:
		print(f1c)
	else:
		print(min(f1c, f2c))


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	matrix = []
	for n in range(N):
		input_string = input()
		matrix.append(input_string)
	count1 = count2 = 0
	for row in range(N):
		for col in range(M):
			if (row + col) % 2 == 0 and matrix[row][col] != '*':
				count1 += 1
			if (row + col) % 2 != 0 and matrix[row][col] != '.':
				count1 += 1
	for row in range(N):
		for col in range(M):
			if (row + col) % 2 == 0 and matrix[row][col] != '.':
				count2 += 1
			if (row + col) % 2 != 0 and matrix[row][col] != '*':
				count2 += 1
	if N * M % 2 == 0:
		print(min(count1, count2))
	else:
		print(count1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	symb = ['*', '.']
	for i in range(n):
		s = input()
		for j in range(m):
			if s[j] != symb[j % 2]:
				ans += 1
		symb = [symb[1], symb[0]]
	if n * m % 2 == 1:
		print(ans)
	else:
		ans = min(ans, n * m - ans)
		print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(input()))
	count1 = 0
	land1 = 0
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0:
				if a[i][j] != '.':
					count1 += 1
			else:
				land1 += 1
				if a[i][j] != '*':
					count1 += 1
	count2 = 0
	land2 = 0
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0:
				land2 += 1
				if a[i][j] != '*':
					count2 += 1
			elif a[i][j] != '.':
				count2 += 1
	if land1 < land2:
		print(count2)
	elif land1 > land2:
		print(count1)
	else:
		print(min(count1, count2))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	comp = {'*': '.', '.': '*'}
	(x, y) = (0, 0)
	bs = '*'
	for i in range(n):
		chk = bs
		bs = comp[bs]
		row = input()
		for j in range(m):
			x += row[j] != chk
			y += row[j] == chk
			chk = comp[chk]
	print(x if m % 2 and n % 2 else min(x, y))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	matrix = [list(input()) for _ in range(n)]
	if n % 2 == 0 or m % 2 == 0:
		(count1, count2) = (0, 0)
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					if matrix[i][j] != '*':
						count1 += 1
					if matrix[i][j] != '.':
						count2 += 1
				else:
					if matrix[i][j] != '*':
						count2 += 1
					if matrix[i][j] != '.':
						count1 += 1
		print(min(count1, count2))
	else:
		count = 0
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					if matrix[i][j] != '*':
						count += 1
				elif matrix[i][j] != '.':
					count += 1
		print(count)


t = int(input())
for test in range(t):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	l1 = []
	for i in range(n):
		l1.append(input())
	total = n * m
	ans1 = 0
	ans2 = 0
	for i in range(n):
		for j in range(m):
			if i + j & 1:
				if l1[i][j] == '.':
					ans2 += 1
				else:
					ans1 += 1
			elif l1[i][j] == '*':
				ans2 += 1
			else:
				ans1 += 1
	if total & 1:
		print(ans1)
	else:
		print(min(ans1, ans2))


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	arr = []
	for i in range(n):
		s = input()
		arr.append(s)
	(o, e) = (0, 0)
	for i in range(n):
		for j in range(m):
			if i % 2 == 0 and j % 2 == 0 and (arr[i][j] == '*'):
				e += 1
			if i % 2 == 0 and j % 2 == 1 and (arr[i][j] == '.'):
				e += 1
			if i % 2 == 1 and j % 2 == 0 and (arr[i][j] == '.'):
				e += 1
			if i % 2 == 1 and j % 2 == 1 and (arr[i][j] == '*'):
				e += 1
			if i % 2 == 0 and j % 2 == 0 and (arr[i][j] == '.'):
				o += 1
			if i % 2 == 0 and j % 2 == 1 and (arr[i][j] == '*'):
				o += 1
			if i % 2 == 1 and j % 2 == 0 and (arr[i][j] == '*'):
				o += 1
			if i % 2 == 1 and j % 2 == 1 and (arr[i][j] == '.'):
				o += 1
	if n % 2 and m % 2:
		print(o)
	else:
		print(min(o, e))


def first_water(n):
	return ''.join(['.' if i % 2 == 0 else '*' for i in range(n)])

def first_land(n):
	return ''.join(['.' if i % 2 == 1 else '*' for i in range(n)])

def compare(seq1, seq2):
	return sum((1 for (a, b) in zip(seq1, seq2) if a != b))
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	S = []
	for l in range(N):
		S.append(input())
	water = first_water(M)
	land = first_land(M)
	cntwater = sum((1 for i in water if i == '*'))
	cntland = sum((1 for i in land if i == '*'))
	res1 = 0
	cnt1 = 0
	for line in range(N):
		if line % 2 == 0:
			res1 += compare(S[line], water)
			cnt1 += cntwater
		else:
			res1 += compare(S[line], land)
			cnt1 += cntland
	res2 = 0
	cnt2 = 0
	for line in range(N):
		if line % 2 == 0:
			res2 += compare(S[line], land)
			cnt2 += cntland
		else:
			res2 += compare(S[line], water)
			cnt2 += cntwater
	if cnt1 < cnt2:
		print(res2)
	elif cnt1 == cnt2:
		print(min(res1, res2))
	else:
		print(res1)


def cnt(m):
	(p, q) = ([0, 0], [0, 0])
	for (i, a) in enumerate(m):
		for (j, e) in enumerate(a):
			if e == '*':
				if (i + j) % 2:
					p[0] += 1
				else:
					q[0] += 1
			elif (i + j) % 2:
				p[1] += 1
			else:
				q[1] += 1
	return (p, q)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mat = []
	for _ in range(n):
		mat.append(input())
	(p, q) = cnt(mat)
	z = n * m
	if z % 2 == 1:
		(a, b) = (n // 2, m // 2)
		x = (a + 1) * (b + 1) + a * b
		y = z - x
		op = x - q[0] + y - p[1]
	else:
		e = m if n % 2 else n
		o = z // e
		x = e // 2 * o
		a = 2 * x - (q[0] + p[1])
		b = 2 * x - (p[0] + q[1])
		op = min(a, b)
	print(op)


def compute(row, column):
	count = 0
	for i in range(n):
		column = row
		for j in range(m):
			if arr[i][j] != column:
				count += 1
			if column == '*':
				column = '.'
			else:
				column = '*'
		if row == '*':
			row = '.'
		else:
			row = '*'
	return count
test_case = int(input())
while test_case:
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(input())
	if n % 2 == 1 and m % 2 == 1:
		count1 = compute('*', '*')
		print(count1)
	else:
		count1 = compute('*', '*')
		count2 = compute('.', '.')
		print(min(count1, count2))
	test_case -= 1


def build(n, m, matrix):
	if n * m % 2 == 0:
		ans1 = 0
		ans2 = 0
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					if matrix[i][j] != '*':
						ans1 += 1
					if matrix[i][j] != '.':
						ans2 += 1
				else:
					if matrix[i][j] != '.':
						ans1 += 1
					if matrix[i][j] != '*':
						ans2 += 1
		return min(ans1, ans2)
	else:
		ans = 0
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					if matrix[i][j] != '*':
						ans += 1
				elif matrix[i][j] != '.':
					ans += 1
		return ans
cases = int(input())
for v in range(cases):
	(n, m) = map(int, input().strip().split())
	matrix = []
	for i in range(n):
		a = list(input())
		matrix.append(a)
	print(build(n, m, matrix))


def fun(x, n, m):
	a = 0
	b = 0
	if m % 2 == 1 and n % 2 == 1:
		for i in range(len(x)):
			for ii in range(len(x[0])):
				if (i + ii) % 2 == 0:
					if x[i][ii] == '*':
						a += 1
					else:
						b += 1
				elif x[i][ii] == '.':
					a += 1
				else:
					b += 1
		print(b)
		return
	elif m != 1 and n != 1:
		for i in range(len(x)):
			for ii in range(len(x[0])):
				if (i + ii) % 2 == 0:
					if x[i][ii] == '*':
						a += 1
					else:
						b += 1
				elif x[i][ii] == '.':
					a += 1
				else:
					b += 1
		print(min(a, b))
		return
for __ in range(int(input())):
	(n, m) = map(int, input().split())
	x = []
	for ___ in range(n):
		a = input()
		x.append(a)
	fun(x, n, m)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		l = list(input())
		a.append(l)
	ans1 = 0
	for i in range(n):
		for j in range(m):
			if i + j & 1 and a[i][j] == '.':
				ans1 += 1
			if (i + j) % 2 == 0 and a[i][j] == '*':
				ans1 += 1
	ans2 = 0
	for i in range(n):
		for j in range(m):
			if i + j & 1 and a[i][j] == '*':
				ans2 += 1
			if (i + j) % 2 == 0 and a[i][j] == '.':
				ans2 += 1
	if m * n & 1:
		print(ans2)
		continue
	print(min(ans1, ans2))


for t in range(int(input())):
	(n, m) = map(int, input().split())
	s = []
	for i in range(n):
		s.append(input())
	(cnt, op1, op2) = (0, 0, 0)
	if n % 2 == 1 and m % 2 == 1:
		ans = 0
		for i in range(n):
			for j in range(m):
				if cnt % 2 == 0 and s[i][j] != '*':
					ans += 1
				if cnt % 2 == 1 and s[i][j] != '.':
					ans += 1
				cnt += 1
		print(ans)
		continue
	for i in range(n):
		for j in range(m):
			if cnt % 2 == 0 and s[i][j] != '*':
				op1 += 1
			if cnt % 2 == 1 and s[i][j] != '.':
				op1 += 1
			if cnt % 2 == 0 and s[i][j] != '.':
				op2 += 1
			if cnt % 2 == 1 and s[i][j] != '*':
				op2 += 1
			cnt += 1
		if m % 2 == 0:
			cnt += 1
	print(min(op1, op2))


for _ in range(int(input())):
	(n, m) = map(int, input().strip().split())
	count1 = 0
	count2 = 0
	for x in range(n):
		arr = list(input())
		for y in range(len(arr)):
			if (y + x) % 2 == 0:
				if arr[y] == '.':
					count1 += 1
			if (x + y) % 2 == 1:
				if arr[y] == '*':
					count1 += 1
		for y in range(len(arr)):
			if (y + x) % 2 == 0:
				if arr[y] == '*':
					count2 += 1
			if (x + y) % 2 == 1:
				if arr[y] == '.':
					count2 += 1
	if n * m % 2 == 0:
		print(min(count1, count2))
	else:
		print(count1)


for _ in range(int(input())):
	sum1 = 0
	(x, y) = map(int, input().split())
	comp = '*'
	if y % 2 != 0 and x % 2 != 0:
		comp = '*'
		bl = True
		cnt = 0
		for i in range(x):
			s = input()
			comp = '*'
			if i % 2 != 0:
				comp = '.'
			for j in s:
				if j != comp:
					cnt += 1
				if bl:
					comp = '.'
					bl = False
				else:
					comp = '*'
					bl = True
		print(cnt)
	else:
		sum1 = 0
		sum2 = 0
		for i in range(x):
			s = input()
			swap1 = '*'
			swap2 = '.'
			if i % 2 != 0:
				(swap1, swap2) = (swap2, swap1)
			for j in s:
				if j != swap1:
					sum1 += 1
				if j != swap2:
					sum2 += 1
				(swap1, swap2) = (swap2, swap1)
		print(min(sum1, sum2))


try:
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		arr = []
		for i in range(n):
			arr.append(input())
		total = n * m
		ans1 = ans2 = 0
		for i in range(n):
			for j in range(m):
				if arr[i][j] == '.' and (i + j) % 2 == 0:
					ans1 += 1
				if arr[i][j] == '*' and (i + j) % 2 == 1:
					ans1 += 1
				if arr[i][j] == '*' and (i + j) % 2 == 0:
					ans2 += 1
				if arr[i][j] == '.' and (i + j) % 2 == 1:
					ans2 += 1
		if total % 2 != 0:
			print(ans1)
			continue
		print(min(ans1, ans2))
except:
	pass


MOD = 1000000007

def si():
	return input()

def ii():
	return int(input())

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

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

def sout(v):
	print(v, end=' ')

def d2b(n):
	return bin(n).replace('0b', '')

def twod(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def vow():
	return ['a', 'e', 'i', 'o', 'u']

def let():
	return [chr(i) for i in range(97, 123)]

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def ispow2(x):
	return x and (not x & x - 1)

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return list(factors)
t = ii()
while t:
	t -= 1
	(n, m) = mi()
	a = []
	for _ in range(n):
		a.append(si())
	if n * m % 2 == 1:
		c = 0
		for i in range(n):
			for j in range(m):
				if i % 2 == 0 and j % 2 == 0 or (i % 2 == 1 and j % 2 == 1):
					if a[i][j] == '.':
						c += 1
				elif a[i][j] == '*':
					c += 1
		print(c)
	else:
		c1 = c2 = 0
		for i in range(n):
			for j in range(m):
				if i % 2 == 0 and j % 2 == 1 or (i % 2 == 1 and j % 2 == 0):
					if a[i][j] == '.':
						c1 += 1
				elif a[i][j] == '*':
					c1 += 1
		for i in range(n):
			for j in range(m):
				if i % 2 == 0 and j % 2 == 0 or (i % 2 == 1 and j % 2 == 1):
					if a[i][j] == '.':
						c2 += 1
				elif a[i][j] == '*':
					c2 += 1
		print(min(c1, c2))


import sys
MOD = 1000000007
import math

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

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

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

def write_line(out):
	return sys.stdout.write(str(out) + '\n')

def calculate(matrix, start, n, m):
	count = 0
	nmatrix = [['.' for i in range(m)] for j in range(n)]
	flag = start
	for i in range(m):
		if flag:
			nmatrix[0][i] = '*'
			if matrix[0][i] == '.':
				count += 1
		elif matrix[0][i] == '*':
			count += 1
		flag ^= 1
	for i in range(1, n):
		for j in range(m):
			if nmatrix[i - 1][j] != '*':
				nmatrix[i][j] = '*'
				if matrix[i][j] == '.':
					count += 1
			elif matrix[i][j] == '*':
				count += 1
	return count

def solve():
	(n, m) = get_ints()
	matrix = []
	for i in range(n):
		matrix.append(list(get_line()))
	if n * m % 2:
		return calculate(matrix, 1, n, m)
	return min(calculate(matrix, 0, n, m), calculate(matrix, 1, n, m))
t = get_int()
while t:
	write_line(solve())
	t -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	land = [0, 0]
	water = [0, 0]
	s = [0] * n
	for i in range(n):
		s[i] = input()
		for j in range(m):
			if s[i][j] == '.':
				water[(i + j) % 2] += 1
			else:
				land[(i + j) % 2] += 1
	if m * n % 2 == 0:
		total = m * n // 2
		ans1 = abs(total - land[0]) + abs(total - water[1])
		ans2 = abs(total - land[1]) + abs(total - water[0])
		print(min(ans1, ans2))
	else:
		total_land = m * n // 2 + 1
		total_water = total_land - 1
		ans = abs(total_land - land[0]) + abs(total_water - water[1])
		print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		row = input()
		arr.append(list(row))
	(mov1, mov2) = (0, 0)
	total = n * m
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and arr[i][j] == '.':
				mov1 += 1
			if (i + j) % 2 != 0 and arr[i][j] == '*':
				mov1 += 1
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and arr[i][j] == '*':
				mov2 += 1
			if (i + j) % 2 != 0 and arr[i][j] == '.':
				mov2 += 1
	if total % 2 == 0:
		print(min(mov1, mov2))
	else:
		print(mov1)


res = [['.', '*', '.', '*', '.', '*', '.', '*', '.', '*'], ['*', '.', '*', '.', '*', '.', '*', '.', '*', '.']]
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	grid = [list(input()) for i in range(n)]
	if n * m % 2:
		r1 = 0
		for i in range(n):
			for j in range(m):
				if i % 2 == 0:
					if res[1][j] != grid[i][j]:
						r1 += 1
				elif res[0][j] != grid[i][j]:
					r1 += 1
		print(r1)
	else:
		r1 = 0
		for i in range(n):
			for j in range(m):
				if i % 2 == 0:
					if res[1][j] != grid[i][j]:
						r1 += 1
				elif res[0][j] != grid[i][j]:
					r1 += 1
		print(min(r1, n * m - r1))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	p = []
	q = []
	(x, y) = (0, 0)
	for j in range(b):
		if j % 2:
			p.append('*')
			q.append('.')
		else:
			p.append('.')
			q.append('*')
	for m in range(a):
		t = input()
		t = list(t)
		if m % 2:
			x += len([1 for i in range(b) if p[i] != t[i]])
			y += len([1 for i in range(b) if q[i] != t[i]])
		else:
			y += len([1 for i in range(b) if p[i] != t[i]])
			x += len([1 for i in range(b) if q[i] != t[i]])
	if a * b % 2 == 0:
		print(min(x, y))
	else:
		print(x)


test = int(input())
for testcase in range(test):
	li = [int(x) for x in input().split()]
	(n, m) = (li[0], li[1])
	arr = []
	for i in range(n):
		l = input()
		arr.append(l)
	c = 0
	for i in range(n):
		if i % 2 == 0:
			for j in range(m):
				if j % 2 == 0:
					if arr[i][j] == '.':
						c += 1
				elif arr[i][j] == '*':
					c += 1
		else:
			for j in range(m):
				if j % 2 == 0:
					if arr[i][j] == '*':
						c += 1
				elif arr[i][j] == '.':
					c += 1
	c1 = 0
	for i in range(n):
		if i % 2 == 1:
			for j in range(m):
				if j % 2 == 0:
					if arr[i][j] == '.':
						c1 += 1
				elif arr[i][j] == '*':
					c1 += 1
		else:
			for j in range(m):
				if j % 2 == 0:
					if arr[i][j] == '*':
						c1 += 1
				elif arr[i][j] == '.':
					c1 += 1
	if n * m % 2 == 0:
		print(min(c, c1))
	else:
		print(c)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input())
	(c, c1) = (0, 0)
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and l[i][j] == '.':
				c += 1
			if (i + j) % 2 != 0 and l[i][j] == '*':
				c += 1
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and l[i][j] == '*':
				c1 += 1
			if (i + j) % 2 != 0 and l[i][j] == '.':
				c1 += 1
	print(c if n * m % 2 != 0 else min(c, c1))


def posGrid(n, m):
	if m % 2:
		g1 = [[''] * m for i in range(n)]
		for r in range(n):
			for c in range(m):
				if (r + c) % 2:
					g1[r][c] = '.'
				else:
					g1[r][c] = '*'
		if n % 2:
			return [g1]
		g2 = []
		for row in g1:
			g2.append(row[:])
		for i in range(0, n, 2):
			(g2[i], g2[i + 1]) = (g2[i + 1], g2[i])
		return [g1, g2]
	else:
		g1 = [[''] * m for i in range(n)]
		g2 = [[''] * m for i in range(n)]
		for r in range(n):
			for c in range(m):
				if (r + c) % 2:
					g1[r][c] = '.'
					g2[r][c] = '*'
				else:
					g1[r][c] = '*'
					g2[r][c] = '.'
		return [g1, g2]

def show(g):
	for grid in g:
		for row in grid:
			print(row)
		print()

def solve(grid, n, m):
	ans = float('inf')
	for Grid in posGrid(n, m):
		part = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] != Grid[i][j]:
					part += 1
		ans = min(ans, part)
	return ans
for case in range(int(input())):
	(n, m) = map(int, input().split())
	grid = []
	for i in range(n):
		grid.append(input())
	ans = solve(grid, n, m)
	print(ans)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
mod = int(1000000000.0) + 7
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = ip()
for _ in range(t):
	(n, m) = inp()
	arr = []
	for i in range(n):
		s = ips()
		arr.append(s)
	ans1 = 0
	for i in range(n):
		if i & 1 == 0:
			for j in range(m):
				if j & 1 == 0:
					if arr[i][j] == '*':
						pass
					else:
						ans1 += 1
				elif arr[i][j] == '.':
					pass
				else:
					ans1 += 1
		else:
			for j in range(m):
				if j & 1 == 0:
					if arr[i][j] == '.':
						pass
					else:
						ans1 += 1
				elif arr[i][j] == '*':
					pass
				else:
					ans1 += 1
	ans2 = 0
	for i in range(n):
		if i & 1 == 1:
			for j in range(m):
				if j & 1 == 0:
					if arr[i][j] == '*':
						pass
					else:
						ans2 += 1
				elif arr[i][j] == '.':
					pass
				else:
					ans2 += 1
		else:
			for j in range(m):
				if j & 1 == 0:
					if arr[i][j] == '.':
						pass
					else:
						ans2 += 1
				elif arr[i][j] == '*':
					pass
				else:
					ans2 += 1
	if n & 1 == 1 and m & 1 == 1:
		ans = ans1
	else:
		ans = min(ans1, ans2)
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().strip().split()))
	grid = []
	for _ in range(n):
		temp = []
		temp = input().strip()
		grid.append(temp)
	count1 = 0
	count2 = 0
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0:
				if grid[i][j] == '.':
					count1 += 1
				else:
					count2 += 1
			elif grid[i][j] == '*':
				count1 += 1
			else:
				count2 += 1
	if n % 2 == 0 or m % 2 == 0:
		print(min(count1, count2))
	else:
		print(count1)


import sys
from collections import defaultdict, deque
input = lambda : sys.stdin.readline().rstrip('\r\n')

def f(B):
	ans1 = ans = 0
	for i in range(n):
		for j in range(m):
			if aa[i][j] != B[i][j]:
				ans += 1
	return ans
a = ['*', '.']
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	aa = [input() for _ in range(n)]
	(s1, s2) = ('', '')
	(b, c) = ([], [])
	(x, y) = (0, 1)
	for i in range(m):
		s1 += a[x]
		s2 += a[y]
		(x, y) = (x ^ 1, y ^ 1)
	(x, y) = (0, 1)
	s = [s1, s2]
	for _ in range(n):
		b.append(s[x])
		c.append(s[y])
		(x, y) = (x ^ 1, y ^ 1)
	ans = f(b)
	if n * m % 2 == 0:
		ans = min(ans, f(c))
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		s = input()
		a.append(s)
	if n * m % 2 == 0:
		c1 = 0
		for i in range(n):
			for j in range(len(a[i])):
				if (i + j) % 2 == 0:
					if a[i][j] == '.':
						c1 += 1
				elif a[i][j] == '*':
					c1 += 1
		c2 = 0
		for i in range(n):
			for j in range(len(a[i])):
				if (i + j) % 2 == 0:
					if a[i][j] == '*':
						c2 += 1
				elif a[i][j] == '.':
					c2 += 1
		print(min(c1, c2))
	else:
		c1 = 0
		for i in range(n):
			for j in range(len(a[i])):
				if (i + j) % 2 == 0:
					if a[i][j] == '.':
						c1 += 1
				elif a[i][j] == '*':
					c1 += 1
		print(c1)


I = input
t = int(I())
for _ in range(t):
	(n, m) = map(int, I().split())
	k = n * m
	c = k // 2
	for i in range(n):
		s = I()
		for j in range(m):
			c += s[j] == '*' and 1 - (i ^ j) % 2 * 2
	print(min((c, k - c)[k & 1:]))