Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef’s girlfriend's birthday is near, so he wants to surprise her by making a special cake for her. Chef knows that his girlfriend likes cherries on the cake, so he puts cherries on the top of the cake, but he was not satisfied. Therefore, he decided to replace some of the cherries to make a beautiful pattern. However, Chef has a lot of other work to do so he decided to ask for your help.

The cherries are of two colors red and green. Now Chef wants the cherries to be placed in such a way that each cherry of one color must be adjacent to only cherries of the other color, two cherries are adjacent if they share a side. Now Chef has asked for your help in making that pattern on the cake.

You can replace any cherry of given color with the other color. But there is a cost for each replacement: if you replace a red cherry with a green one, the cost is 5 units and if you replace a green cherry with a red one, the cost is 3 units.

Help your friend Chef by making the cake special with minimum cost.

------ 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, where N × M are the dimensions of the cake.
Each of the next N lines contains a string of length M.

------ Output ------ 

For each test case, output the minimum cost required to make the cake special.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N, M ≤ 100$
$each string consists only of letters 'R' and 'G' denoting red and green cherries respectively

----- Sample Input 1 ------ 
2
4 5
RGRGR
GRGRG
RGRGR
GRGRG
2 3
RRG
GGR
----- Sample Output 1 ------ 
0
8

Difficulty: MEDIUM
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
for tc in range(int(input())):
	(n, m) = map(int, input().split())
	(fw, sw) = (0, 0)
	for i in range(n):
		s = input()
		l = len(s)
		if i % 2 == 0:
			for j in range(l):
				if j % 2 == 0:
					if s[j] == 'G':
						fw += 3
					else:
						sw += 5
				elif s[j] == 'G':
					sw += 3
				else:
					fw += 5
		else:
			for j in range(l):
				if j % 2 == 0:
					if s[j] == 'R':
						fw += 5
					else:
						sw += 3
				elif s[j] == 'R':
					sw += 5
				else:
					fw += 3
	print(min(fw, sw))


T = int(input())
sol1 = 'RG' * 50
sol2 = 'GR' * 50
for _ in range(T):
	cost1 = 0
	cost2 = 0
	cost_map = {'R': 5, 'G': 3}
	(N, M) = map(int, input().split(' '))
	for i in range(N):
		row = input()
		for (cherry, val1) in zip(row, sol1):
			if cherry != val1:
				cost1 += cost_map[cherry]
			else:
				cost2 += cost_map[cherry]
		(sol1, sol2) = (sol2, sol1)
	print(min(cost2, cost1))


n = int(input())
for _ in range(n):
	(w, h) = map(int, input().split())
	even = {'R': 0, 'G': 0}
	odd = {'R': 0, 'G': 0}
	for i in range(w):
		row = input()
		for (j, char) in enumerate(row):
			if (i + j) % 2:
				even[char] += 1
			else:
				odd[char] += 1
	cost_a = even['R'] * 5 + odd['G'] * 3
	cost_b = odd['R'] * 5 + even['G'] * 3
	print(min(cost_a, cost_b))


n = int(input())
for _ in range(n):
	(w, h) = map(int, input().split())
	cost_a = 0
	cost_b = 0
	data = []
	for i in range(w):
		data.append(input())
	for i in range(w):
		for j in range(h):
			char = data[i][j]
			is_even_idx = (i + j) % 2
			if char == 'R' and is_even_idx:
				cost_a += 5
			elif char == 'R' and (not is_even_idx):
				cost_b += 5
			elif char == 'G' and is_even_idx:
				cost_b += 3
			elif char == 'G' and (not is_even_idx):
				cost_a += 3
	print(min(cost_a, cost_b))


def minimum_cost(x, y, pattern):
	cost_a = 0
	cost_b = 0
	for i in range(y):
		for j in range(x):
			char = pattern[i][j]
			is_even_idx = (i + j) % 2 == 0
			if char == 'R' and is_even_idx:
				cost_a += 5
			elif char == 'R' and (not is_even_idx):
				cost_b += 5
			elif char == 'G' and is_even_idx:
				cost_b += 3
			elif char == 'G' and (not is_even_idx):
				cost_a += 3
	return min(cost_a, cost_b)
cases = int(input())
for _ in range(cases):
	(y, x) = map(int, input().split())
	patterns = []
	for i in range(y):
		patterns.append(input())
	print(minimum_cost(x, y, patterns))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	x1 = 0
	x2 = 0
	for j in range(n):
		s = input()
		if j % 2 == 0:
			for i in range(len(s)):
				if i % 2 == 0:
					if s[i] == 'R':
						x1 += 5
					else:
						x2 += 3
				elif s[i] == 'R':
					x2 += 5
				else:
					x1 += 3
		else:
			for i in range(len(s)):
				if i % 2 == 0:
					if s[i] == 'G':
						x1 += 3
					else:
						x2 += 5
				elif s[i] == 'G':
					x2 += 3
				else:
					x1 += 5
	print(min(x1, x2))


def minimum_cost(x, y, pattern):
	cost_a = 0
	cost_b = 0
	for i in range(y):
		for j in range(x):
			char = pattern[i][j]
			is_even_idx = (i + j + 1) % 2 == 0
			if char == 'R' and is_even_idx:
				cost_a += 5
			elif char == 'R' and (not is_even_idx):
				cost_b += 5
			elif char == 'G' and is_even_idx:
				cost_b += 3
			elif char == 'G' and (not is_even_idx):
				cost_a += 3
	return min(cost_a, cost_b)
test_cases_count = int(input())
for i in range(test_cases_count):
	dimensions = input().split()
	y = int(dimensions[0])
	x = int(dimensions[1])
	patterns = []
	for i in range(y):
		patterns.append(input())
	print(minimum_cost(x, y, patterns))


def test_func():
	(n, m) = map(lambda x: int(x), str(input()).split(' '))
	string_list = []
	for i in range(n):
		string_list.append(input())
	new_string = ''.join(string_list)
	ideal_string_1 = []
	ideal_string_2 = []
	counter = 0
	for i in range(n):
		ideal_string_1 += map(lambda x: 'R' if x % 2 else 'G', range(m)) if counter % 2 else map(lambda x: 'G' if x % 2 else 'R', range(m))
		ideal_string_2 += map(lambda x: 'G' if x % 2 else 'R', range(m)) if counter % 2 else map(lambda x: 'R' if x % 2 else 'G', range(m))
		counter += 1
	ideal_string_1 = ''.join(ideal_string_1)
	ideal_string_2 = ''.join(ideal_string_2)
	if new_string in [ideal_string_1, ideal_string_2]:
		print(0)
		return
	string_1_change = 0
	string_2_change = 0
	cost1 = 0
	cost2 = 0
	for i in range(m * n):
		if ideal_string_1[i] != new_string[i]:
			string_1_change += 1
			cost1 += 5 if new_string[i] == 'R' else 3
		if ideal_string_2[i] != new_string[i]:
			string_2_change += 1
			cost2 += 5 if new_string[i] == 'R' else 3
	print(min(cost1, cost2))
	return
	print(cost)
T = int(input())
for i in range(T):
	test_func()


t = input()
for c in range(0, int(t)):
	(n, m) = map(int, input().split())
	arr = []
	(a, b) = (0, 0)
	for i in range(n):
		temp = input()
		arr.append(temp)
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and arr[i][j] != 'R':
				a += 3
			if (i + j) % 2 == 1 and arr[i][j] != 'G':
				a += 5
			if (i + j) % 2 == 0 and arr[i][j] != 'G':
				b += 5
			if (i + j) % 2 == 1 and arr[i][j] != 'R':
				b += 3
	print(min(a, b))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input())
	(a, b) = (0, 0)
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and l[i][j] != 'R':
				a += 3
			elif (i + j) % 2 == 1 and l[i][j] != 'G':
				a += 5
			if (i + j) % 2 == 0 and l[i][j] != 'G':
				b += 5
			elif (i + j) % 2 == 1 and l[i][j] != 'R':
				b += 3
	print(min(a, b))


tst = int(input())
for i in range(tst):
	(n, m) = map(int, input().split())
	arr = []
	(a, b) = (0, 0)
	for j in range(n):
		st = list(input())
		arr.append(st)
	for j in range(n):
		for k in range(m):
			if (j + k) % 2 == 0 and arr[j][k] != 'R':
				a = a + 3
			if (j + k) % 2 == 1 and arr[j][k] != 'G':
				a = a + 5
			if (j + k) % 2 == 0 and arr[j][k] != 'G':
				b = b + 5
			if (j + k) % 2 == 1 and arr[j][k] != 'R':
				b = b + 3
	ans = min(a, b)
	print(ans)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	(c1, c2) = (0, 0)
	for i in range(N):
		l = input()
		for j in range(M):
			if i % 2 == 0 and j % 2 == 0 and (l[j] == 'G'):
				c1 += 3
			elif i % 2 == 0 and j % 2 != 0 and (l[j] == 'R'):
				c1 += 5
			elif i % 2 != 0 and j % 2 == 0 and (l[j] == 'R'):
				c1 += 5
			elif i % 2 != 0 and j % 2 != 0 and (l[j] == 'G'):
				c1 += 3
		for j in range(M):
			if i % 2 == 0 and j % 2 == 0 and (l[j] == 'R'):
				c2 += 5
			elif i % 2 == 0 and j % 2 != 0 and (l[j] == 'G'):
				c2 += 3
			elif i % 2 != 0 and j % 2 == 0 and (l[j] == 'G'):
				c2 += 3
			elif i % 2 != 0 and j % 2 != 0 and (l[j] == 'R'):
				c2 += 5
	print(min(c1, c2))


for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	g = 0
	r = 0
	for i in range(n):
		s = input()
		if i % 2 == 0:
			for j in range(m):
				if j % 2 == 0:
					if s[j] == 'R':
						g += 5
					else:
						r += 3
				elif s[j] == 'G':
					g += 3
				else:
					r += 5
		else:
			for j in range(m):
				if j % 2 == 0:
					if s[j] == 'G':
						g += 3
					else:
						r += 5
				elif s[j] == 'R':
					g += 5
				else:
					r += 3
	if g > r:
		print(r)
	else:
		print(g)


tests = int(input())
for i in range(tests):
	(rows, cols) = map(int, input().split())
	ans1 = 0
	ans2 = 0
	for j in range(rows):
		string = input()
		for k in range(cols):
			if (j + k) % 2 == 0:
				if string[k] != 'G':
					ans1 += 5
				if string[k] != 'R':
					ans2 += 3
			else:
				if string[k] != 'R':
					ans1 += 3
				if string[k] != 'G':
					ans2 += 5
	print(min(ans1, ans2))


t = int(input())

def pen(c):
	if c == 'R':
		return 5
	return 3
for q in range(t):
	(n, m) = map(int, input().split())
	s = []
	for i in range(n):
		s.append('')
		s[i] = input()
	(a, b) = ([], [])
	for i in range(n):
		a.append([])
		b.append([])
		for j in range(m):
			if (i + j) % 2 == 0:
				a[i].append('R')
				b[i].append('G')
			else:
				a[i].append('G')
				b[i].append('R')
	(pena, penb) = (0, 0)
	for i in range(n):
		for j in range(m):
			if s[i][j] == a[i][j]:
				penb += pen(s[i][j])
			else:
				pena += pen(s[i][j])
	print(min(pena, penb))


a = int(input())
for i in range(a):
	b = input().split(' ')
	c = int(b[0])
	d = int(b[1])
	count1 = 0
	count2 = 0
	for i in range(c):
		g = input()
		for n in range(d):
			o = i + n
			if o % 2 == 0:
				if g[n] == 'G':
					count1 += 3
				else:
					count2 += 5
			elif g[n] == 'G':
				count2 += 3
			else:
				count1 += 5
	op1 = min(count1, count2)
	print(op1)


T = int(input())
for x in range(T):
	(N, M) = map(int, input().split())
	a = []
	(b, c) = (0, 0)
	for y in range(N):
		p = input()
		a.append(p)
	for z in range(N):
		for i in range(M):
			if (z + i) % 2 == 0 and a[z][i] != 'R':
				b += 3
			if (z + i) % 2 == 1 and a[z][i] != 'G':
				b += 5
			if (z + i) % 2 == 0 and a[z][i] != 'G':
				c += 5
			if (z + i) % 2 == 1 and a[z][i] != 'R':
				c += 3
	print(min(b, c))


test_cases = int(input())
for i in range(test_cases):
	(n, l) = map(int, input().split())
	a = []
	(b, c) = (0, 0)
	for i in range(n):
		string = input()
		a.append(string)
	for j in range(n):
		for k in range(l):
			if (j + k) % 2 == 0 and a[j][k] != 'R':
				b += 3
			if (j + k) % 2 == 1 and a[j][k] != 'G':
				b += 5
			if (j + k) % 2 == 0 and a[j][k] != 'G':
				c += 5
			if (j + k) % 2 == 1 and a[j][k] != 'R':
				c += 3
	print(min(b, c))


for T in range(int(input())):
	(N, M) = map(int, input().split())
	red_cherries = 0
	green_cherries = 0
	for i in range(N):
		a = input()
		if i % 2 == 0:
			for k in range(M):
				if k % 2 == 0 and a[k] == 'R':
					green_cherries += 5
				elif k % 2 != 0 and a[k] == 'G':
					green_cherries += 3
				if k % 2 == 0 and a[k] == 'G':
					red_cherries += 3
				elif k % 2 != 0 and a[k] == 'R':
					red_cherries += 5
		elif i % 2 != 0:
			for k in range(M):
				if k % 2 == 0 and a[k] == 'G':
					green_cherries += 3
				elif k % 2 != 0 and a[k] == 'R':
					green_cherries += 5
				if k % 2 == 0 and a[k] == 'R':
					red_cherries += 5
				elif k % 2 != 0 and a[k] == 'G':
					red_cherries += 3
	if red_cherries < green_cherries:
		print(red_cherries)
	else:
		print(green_cherries)


t = int(input())

def pattern(c):
	if c == 'R':
		return 5
	return 3
for q in range(t):
	(n, m) = map(int, input().split())
	str_list = []
	for i in range(n):
		str_list.append('')
		str_list[i] = input()
	(a, b) = ([], [])
	for i in range(n):
		a.append([])
		b.append([])
		for j in range(m):
			if (i + j) % 2 == 0:
				a[i].append('R')
				b[i].append('G')
			else:
				a[i].append('G')
				b[i].append('R')
	(pattern1, pattern2) = (0, 0)
	for i in range(n):
		for j in range(m):
			if str_list[i][j] == a[i][j]:
				pattern2 += pattern(str_list[i][j])
			else:
				pattern1 += pattern(str_list[i][j])
	print(min(pattern1, pattern2))


t = int(input())
for k in range(t):
	(n, m) = map(int, input().split())
	r = 0
	g = 0
	for i in range(n):
		a = input()
		if i % 2 == 0:
			for j in range(m):
				if j % 2 == 0 and a[j] == 'R':
					g += 5
				elif j % 2 != 0 and a[j] == 'G':
					g += 3
				if j % 2 == 0 and a[j] == 'G':
					r += 3
				elif j % 2 != 0 and a[j] == 'R':
					r += 5
		else:
			for j in range(m):
				if j % 2 == 0 and a[j] == 'G':
					g += 3
				elif j % 2 != 0 and a[j] == 'R':
					g += 5
				if j % 2 == 0 and a[j] == 'R':
					r += 5
				elif j % 2 != 0 and a[j] == 'G':
					r += 3
	if g > r:
		print(r)
	else:
		print(g)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	red = 0
	green = 0
	for i in range(n):
		string = input()
		if i % 2 == 0:
			for l in range(m):
				if l % 2 == 0 and string[l] == 'R':
					green += 5
				elif l % 2 != 0 and string[l] == 'G':
					green += 3
				if l % 2 == 0 and string[l] == 'G':
					red += 3
				elif l % 2 != 0 and string[l] == 'R':
					red += 5
		elif i % 2 != 0:
			for l in range(m):
				if l % 2 == 0 and string[l] == 'G':
					green += 3
				elif l % 2 != 0 and string[l] == 'R':
					green += 5
				if l % 2 == 0 and string[l] == 'R':
					red += 5
				elif l % 2 != 0 and string[l] == 'G':
					red += 3
	if red < green:
		print(red)
	else:
		print(green)


t = int(input())
for i in range(t):
	ans1 = 0
	ans2 = 0
	(n, m) = map(int, input().split())
	x = []
	for j in range(n):
		s = input()
		x += [s]
	for k in range(n):
		for j in range(m):
			if k % 2 == 0:
				if j % 2 == 0:
					if x[k][j] == 'G':
						ans1 += 3
					else:
						ans2 += 5
				elif x[k][j] == 'R':
					ans1 += 5
				else:
					ans2 += 3
			elif j % 2 == 0:
				if x[k][j] == 'G':
					ans2 += 3
				else:
					ans1 += 5
			elif x[k][j] == 'R':
				ans2 += 5
			else:
				ans1 += 3
	print(min(ans1, ans2))


for _ in range(int(input())):
	(N, M) = [int(s) for s in input().split()]
	cost1 = cost2 = 0
	for i in range(N):
		for (j, c) in enumerate(input()):
			if i + j & 1 == (c != 'R'):
				cost2 += 5 if c == 'R' else 3
			else:
				cost1 += 5 if c == 'R' else 3
	print(min(cost1, cost2))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for _ in range(n):
		ele = list(input())
		arr.append(ele)
	a = 0
	b = 0
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0 and arr[i][j] != 'R':
				a += 3
			if (i + j) % 2 == 1 and arr[i][j] != 'G':
				a += 5
			if (i + j) % 2 == 0 and arr[i][j] != 'G':
				b += 5
			if (i + j) % 2 == 1 and arr[i][j] != 'R':
				b += 3
	print(min(a, b))


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(input())
	r = 0
	g = 0
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 0:
				if arr[i][j] != 'R':
					r += 1
			elif arr[i][j] != 'G':
				g += 1
	r_l = int(math.ceil(n * m / 2))
	r_g = m * n - r_l
	ans = min(3 * r + 5 * g, 5 * (r_l - r) + 3 * (r_g - g))
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(c1, c2) = (0, 0)
	for i in range(n):
		l = input()
		for j in range(m):
			if (i + j) % 2 == 0:
				if l[j] == 'G':
					c1 += 3
				else:
					c2 += 5
			elif l[j] == 'G':
				c2 += 3
			else:
				c1 += 5
	print(min(c1, c2))


import sys
input = sys.stdin.readline

def rii():
	return range(int(input().strip()))

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

def mii():
	return map(int, input().strip().split(' '))

def lmii():
	return list(map(int, input().strip().split(' ')))

def si():
	return str(input().strip())
conversion_cost = {('G', 'R'): 3, ('R', 'G'): 5, ('G', 'G'): 0, ('R', 'R'): 0}
chars = ['G', 'R']

def make_alternating(ch, l):
	return ''.join([chars[(x + ch) % 2] for x in range(l)])

def solve(*args):
	(n, m, grid) = args
	(c1, c2) = (0, 0)
	for i in range(n):
		c1 += sum([conversion_cost[x] for x in zip(grid[i], make_alternating(i % 2, m))])
		c2 += sum([conversion_cost[x] for x in zip(grid[i], make_alternating((i + 1) % 2, m))])
	return min(c1, c2)

def do_codechef():
	for t in rii():
		(n, m) = mii()
		grid = list()
		for _ in range(n):
			grid.append(si())
		print(solve(n, m, grid))
do_codechef()
exit()