Chef is playing an easier variation of the board game ‘Risk’ with his friend Mike. There is an $N * M$ grid, depicting the world map. Each cell of the grid is either $1$ or $0$ where $1$ denotes that there is land on this cell, while $0$ denotes water. 

In a turn, a player can capture an uncaptured cell that has land, and keep capturing neighbouring cells that share a side with it if they are on land. A cell once captured by a player can't be captured again by another player. The game continues till no uncaptured cell has land. Each player wants to be in control of as many cells of land as possible in total when the game finishes. Find the maximum number of cells of land that Chef can capture if he plays second, and both players play optimally. 

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow.
Each testcase contains $N + 1$ lines of input.
First line will contain $2$ space separated integers $N$ and $M$ denoting the size of the grid. 
Each of the next $N$ lines contains a binary string of length $M$ depicting the map. 

------ Output: ------
For each testcase, output in a single line answer to the problem.

------ Constraints  ------
$1 ≤ N, M ≤ 10^{5}$
Each character in the grid is either $0$ or $1$
There's atleast $1$ land on the grid
Sum of $N * M$ over all testcases is almost $10^{6}$.

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

4 4

1001

0110

0110

1001

2 2

11

11

3 3

100

010

001
----- Sample Output 1 ------ 
2

0

1
----- explanation 1 ------ 
In test case 1, if both players play optimally, it takes $5$ steps to finish the game:

Step 1: First Mike chooses the cells $\{(2, 2), (2, 3), (3, 2), (3, 3)\}$ adding $4$ to his score.

Step 2: Second Chef chooses the cell $\{(1, 1)\}$ adding $1$ to his score.

Step 3: Next Mike chooses the cell $\{(1, 4)\}$ adding $1$ to his score.

Step 4: Next Chef chooses the cell $\{(4, 1)\}$ adding $1$ to his score.

Step 5: Finally, Mike chooses the cell $\{(4, 4)\}$ adding $1$ to his score.

Hence total score of Chef is $1 + 1 = 2$.

Source: codechef | Difficulty: HARD
Tags: Sorting

Graph algorithms

Graph traversal

Greedy algorithms


Solutions:
import sys
sys.setrecursionlimit(10 ** 8)
x4 = [-1, 0, 1, 0]
y4 = [0, 1, 0, -1]

def dfs(i, j, count):
	if i < 0 or j < 0 or i >= r or (j >= c):
		return
	if mat[i][j] == 0:
		return
	mat[i][j] = 0
	count[0] += 1
	for d in range(4):
		ni = i + x4[d]
		nj = j + y4[d]
		dfs(ni, nj, count)
t = int(input())
for x in range(t):
	(r, c) = map(int, input().split())
	mat = []
	for i in range(r):
		s = input()
		ls = [int(i) for i in s]
		mat.append(ls)
	ans = []
	for i in range(r):
		for j in range(c):
			if mat[i][j] == 1:
				count = [0]
				dfs(i, j, count)
				ans.append(count[0])
	ans.sort(reverse=True)
	k = len(ans)
	cnt = 0
	for i in range(1, k, 2):
		cnt += ans[i]
	print(cnt)


from sys import setrecursionlimit
setrecursionlimit(100000)

def get_count(a, index, n, m):
	if a[index[0]][index[1]] == 0:
		return 0
	a[index[0]][index[1]] = 0
	ans = 1
	if index[0] - 1 >= 0 and a[index[0] - 1][index[1]]:
		ans += get_count(a, (index[0] - 1, index[1]), n, m)
	if index[0] + 1 < n and a[index[0] + 1][index[1]]:
		ans += get_count(a, (index[0] + 1, index[1]), n, m)
	if index[1] - 1 >= 0 and a[index[0]][index[1] - 1]:
		ans += get_count(a, (index[0], index[1] - 1), n, m)
	if index[1] + 1 < m and a[index[0]][index[1] + 1]:
		ans += get_count(a, (index[0], index[1] + 1), n, m)
	return ans
for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for _ in range(n):
		a.append(list(map(int, input())))
	output = []
	for i in range(n):
		for j in range(m):
			if a[i][j]:
				temp = get_count(a, (i, j), n, m)
				if temp > 0:
					output.append(temp)
	print(sum(sorted(output, reverse=True)[1::2]))


from cmath import pi
from distutils import extension
import sys
from math import gcd, sqrt, log10, log2, floor, ceil
from collections import deque, defaultdict
from tkinter.tix import Tree
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def il(sep=' '):
	return [int(a) for a in input().strip().split(sep)]

def ip():
	return input().strip()

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

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7

def dfs(mat, x, y, dx, dy, c):
	mat[x][y] = 0
	for i in range(4):
		if 0 <= x + dx[i] < len(mat) and 0 <= y + dy[i] < len(mat[0]) and (mat[x + dx[i]][y + dy[i]] == 1):
			c[0] += 1
			dfs(mat, x + dx[i], y + dy[i], dx, dy, c)
for _ in range(ii()):
	(n, m) = il()
	mat = []
	for l in range(n):
		re = ip()
		li = []
		for k in re:
			li.append(int(k))
		mat.append(li)
	ans = []
	dx = [-1, 1, 0, 0]
	dy = [0, 0, 1, -1]
	for i in range(n):
		for j in range(m):
			if mat[i][j] == 1:
				c = [1]
				dfs(mat, i, j, dx, dy, c)
				ans.append(c[0])
	ans.sort(reverse=True)
	res = 0
	for l in range(1, len(ans), 2):
		res = res + ans[l]
	ot(res)


from sys import setrecursionlimit
setrecursionlimit(100000)
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	arr = []
	for _ in range(n):
		arr.append(list(map(int, list(input()))))
	area = []

	def dfs(x, y):
		arr[x][y] = 0
		res = 1
		for (a, b) in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
			if n > a >= 0 and m > b >= 0 and arr[a][b]:
				res += dfs(a, b)
		return res
	for i in range(n):
		for j in range(m):
			if arr[i][j]:
				area.append(dfs(i, j))
	print(sum(sorted(area, reverse=True)[1::2]))


def funcConnected(Map, pos):
	count = 0
	p = []
	moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
	p.append(pos)
	while len(p) != 0:
		point = p.pop()
		count += 1
		for (dx, dy) in moves:
			x = point[0] + dx
			y = point[1] + dy
			if x >= 0 and y >= 0 and (x < len(Map)) and (y < len(Map[x])):
				if Map[x][y] == '1':
					Map[x][y] = '0'
					p.append(tuple([x, y]))
	if count > 1:
		count -= 1
	return count
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	Map = []
	for i in range(n):
		inp = list(input())
		Map.append(inp)
	sizes = []
	for i in range(n):
		for j in range(m):
			if Map[i][j] == '1':
				sizes.append(funcConnected(Map, [i, j]))
	chef = 0
	sizes.sort(reverse=True)
	for i in range(1, len(sizes), 2):
		chef += sizes[i]
	print(chef)


import numpy as np
for i in range(int(input())):
	(n, m) = map(int, input().split())
	www = []
	for ii in range(n):
		www += [[int(iit) for iit in input()]]
	www = np.array(www)
	col = 2
	for ii in range(n):
		for jj in range(m):
			if www[ii][jj] == 1:
				col += 1
				st = []
				www[ii][jj] = col
				if ii != 0:
					st += [(ii - 1, jj)]
				if jj != 0:
					st += [(ii, jj - 1)]
				if ii != n - 1:
					st += [(ii + 1, jj)]
				if jj != m - 1:
					st += [(ii, jj + 1)]
				while len(st) != 0:
					q = st.pop()
					(iii, jjj) = q
					if www[iii, jjj] == 1:
						if iii != 0:
							st += [(iii - 1, jjj)]
						if jjj != 0:
							st += [(iii, jjj - 1)]
						if iii != n - 1:
							st += [(iii + 1, jjj)]
						if jjj != m - 1:
							st += [(iii, jjj + 1)]
						www[iii][jjj] = col
	(xxx, yyy) = np.unique([jh for hj in www for jh in hj], return_counts=True)
	if xxx[0] == 0:
		yyy = yyy[1:]
	res = 0
	for (u, uu) in enumerate(np.sort(yyy)[::-1]):
		if u % 2 == 1:
			res += uu
	print(res)


import collections

def validIndex(i, j, n, m):
	if i in range(0, n) and j in range(0, m):
		return True
	return False

def chefScore(mat, n, m):
	res_arr = []
	for i in range(n):
		for j in range(m):
			if mat[i][j] == '1':
				q = collections.deque([[i, j]])
				count = 0
				while len(q) > 0:
					s = q.pop()
					(l, k) = (s[0], s[1])
					if validIndex(l, k, n, m) and mat[l][k] == '1':
						count += 1
						q.appendleft([l + 1, k])
						q.appendleft([l - 1, k])
						q.appendleft([l, k + 1])
						q.appendleft([l, k - 1])
						mat[l][k] = '0'
				res_arr.append(count)
	res_arr.sort(reverse=True)
	chef_score = 0
	if len(res_arr) < 2:
		return 0
	for i in range(1, len(res_arr), 2):
		chef_score += res_arr[i]
	return chef_score
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(list(input()))
	print(chefScore(arr, n, m))


dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def valid(x, y):
	if 0 <= x < n and 0 <= y < m and (visited[x][y] == False) and (l[x][y] == '1'):
		return True
	return False

def dfs(nodex, nodey):
	visited[nodex][nodey] = True
	stack = [[nodex, nodey]]
	c = 1
	while stack:
		(nodex, nodey) = stack.pop()
		for i in range(4):
			if valid(nodex + dx[i], nodey + dy[i]):
				newx = nodex + dx[i]
				newy = nodey + dy[i]
				visited[newx][newy] = True
				c = c + 1
				stack.append([newx, newy])
	return c
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		k = list(input())
		l.append(k)
	visited = [[False for i in range(m)] for j in range(n)]
	ans = []
	for i in range(n):
		for j in range(m):
			if visited[i][j] == False and l[i][j] == '1':
				c = dfs(i, j)
				ans.append(c)
	ans.sort(reverse=True)
	n = len(ans)
	s = 0
	for i in range(n):
		if i % 2:
			s = s + ans[i]
	print(s)


import sys
sys.setrecursionlimit(1000000)

def dfs(i, j):
	vi[i][j] = 1
	c[0] += 1
	for (x, y) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
		if x >= 0 and y >= 0 and (x < n) and (y < m) and (a[x][y] == 1) and (vi[x][y] == 0):
			dfs(x, y)
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input())))
	vi = [[0 for i in range(m)] for j in range(n)]
	co = []
	for i in range(n):
		for j in range(m):
			if a[i][j] == 1 and vi[i][j] == 0:
				c = [0]
				dfs(i, j)
				co.append(c[0])
	co.sort()
	co.reverse()
	fc = 0
	for i in range(len(co)):
		if i % 2 != 0:
			fc += co[i]
	print(fc)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

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

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

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

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def solve():

	def valid(a, b):
		if a >= n or b >= m or a < 0 or (b < 0):
			return False
		if l[a][b] == '0' or (a, b) in visited:
			return False
		return True

	def dfs(i, j):
		stack = [(i, j)]
		visited[i, j] = 1
		s = 1
		while stack:
			(a, b) = stack.pop()
			for i in range(4):
				(x, y) = (a + dx[i], b + dy[i])
				if valid(x, y):
					stack.append((x, y))
					visited[x, y] = 1
					s += 1
		return s
	ans = 0
	(n, m) = mp()
	l = [st() for i in range(n)]
	visited = defaultdict(int)
	cur = []
	for i in range(n):
		for j in range(m):
			if l[i][j] == '1' and (i, j) not in visited:
				x = dfs(i, j)
				cur.append(x)
	cur.sort(reverse=True)
	for i in range(1, len(cur), 2):
		ans += cur[i]
	pr(ans)
for _ in range(inp()):
	solve()


def fetch(stack, arr, visited, i, j, n, m, cnt):
	if i >= 0 and j >= 0 and (i < n) and (j < m):
		if visited[i][j] == '0' and arr[i][j] == '1':
			visited[i][j] = '1'
			stack.append([i, j])
			cnt += 1
		else:
			visited[i][j] = '1'
		return cnt
	else:
		return cnt
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(list(input().strip()))
	visited = []
	for i in range(n):
		visited.append(['0'] * m)
	stack = []
	cnt = 0
	ConnComp = []
	for i in range(n):
		for j in range(m):
			if visited[i][j] == '0' and arr[i][j] == '1':
				stack.append([i, j])
				visited[i][j] = '1'
				cnt += 1
				while stack:
					(x, y) = stack.pop(0)
					cnt = fetch(stack, arr, visited, x + 1, y, n, m, cnt)
					cnt = fetch(stack, arr, visited, x, y + 1, n, m, cnt)
					cnt = fetch(stack, arr, visited, x - 1, y, n, m, cnt)
					cnt = fetch(stack, arr, visited, x, y - 1, n, m, cnt)
				ConnComp.append(cnt)
				cnt = 0
	ConnComp.sort(reverse=True)
	ans = 0
	for i in range(len(ConnComp)):
		if i % 2 == 1:
			ans += ConnComp[i]
	print(ans)


def is_inside(x, y, n, m):
	return x >= 0 and x < n and (y >= 0) and (y < m)

def find_connected_lands_length(cells, i, j, n, m):
	q = []
	q.append((i, j))
	cells[i][j] = '0'
	neighbour_offset = [(0, 1), (0, -1), (1, 0), (-1, 0)]
	connected_lands_length = 0
	while len(q) > 0:
		(x, y) = q.pop(0)
		connected_lands_length += 1
		for (dx, dy) in neighbour_offset:
			if is_inside(x + dx, y + dy, n, m) and cells[x + dx][y + dy] == '1':
				q.append((x + dx, y + dy))
				cells[x + dx][y + dy] = '0'
	return connected_lands_length
t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	cells = []
	for i in range(n):
		cells.append(input())
	cells = [list(cell) for cell in cells]
	connected_lands = []
	for i in range(n):
		for j in range(m):
			if cells[i][j] == '1':
				connected_lands.append(find_connected_lands_length(cells, i, j, n, m))
	connected_lands.sort(reverse=True)
	chef_lands = 0
	for i in range(1, len(connected_lands), 2):
		chef_lands += connected_lands[i]
	print(chef_lands)


from collections import defaultdict as dd
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	t = []
	for i in range(n):
		b = []
		w = str(input())
		for j in range(m):
			b.append(int(w[j]))
		a.append(list(b))
	d = dd(list)
	k = 0
	for i in range(n):
		for j in range(m):
			if a[i][j] == 1:
				l = i * m + j
				k += 1
				t.append(l)
				if j + 1 < m:
					if a[i][j + 1] == 1:
						d[l].append(i * m + (j + 1))
						d[i * m + (j + 1)].append(l)
				if i + 1 < n:
					if a[i + 1][j] == 1:
						d[l].append((i + 1) * m + j)
						d[(i + 1) * m + j].append(l)
	v = {}
	ap = {}
	for i in t:
		v[i] = 0
		ap[i] = 0
	r = []
	for i in t:
		if v[i] == 0:
			s = []
			c = 0
			s.append(i)
			ap[i] = 1
			while True:
				if c >= len(s):
					break
				if v[s[c]] == 0:
					v[s[c]] = 1
					for j in d[s[c]]:
						if ap[j] == 0:
							s.append(j)
							ap[j] = 1
				c += 1
			r.append(len(s))
	r.sort(reverse=True)
	f = 0
	for i in range(len(r)):
		if i & 1 == 1:
			f += r[i]
	print(f)


import sys
sys.setrecursionlimit(10 ** 9)

def ma(i, j):
	if i >= 0 and i < n and (j >= 0) and (j < m):
		l[i][j] = '0'
		g = 1
		if i - 1 >= 0 and l[i - 1][j] == '1':
			g += ma(i - 1, j)
		if i + 1 < n and l[i + 1][j] == '1':
			g += ma(i + 1, j)
		if j - 1 >= 0 and l[i][j - 1] == '1':
			g += ma(i, j - 1)
		if j + 1 < m and l[i][j + 1] == '1':
			g += ma(i, j + 1)
		return g
	else:
		return 0
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(list(input().strip()))
	x = []
	y = 1
	for i in range(n):
		for j in range(m):
			if l[i][j] == '1':
				x.append(int(ma(i, j)))
	x.sort(reverse=True)
	e = 0
	for i in range(len(x)):
		if i % 2 != 0:
			e += x[i]
	print(e)


from sys import setrecursionlimit
setrecursionlimit(100000)

def f(mat, i, j, m, n):
	c = 0
	if i >= 0 and i < m and (j >= 0) and (j < n) and mat[i][j]:
		mat[i][j] = 0
		c += 1
		c += f(mat, i + 1, j, m, n)
		c += f(mat, i, j + 1, m, n)
		c += f(mat, i - 1, j, m, n)
		c += f(mat, i, j - 1, m, n)
	return c
T = int(input())
for i in range(T):
	(m, n) = map(int, input().split())
	v = []
	mat = [list(map(int, list(input()))) for i in range(m)]
	for x in range(m):
		for y in range(n):
			if mat[x][y]:
				v.append(f(mat, x, y, m, n))
	s = 0
	v.sort(reverse=1)
	for j in range(1, len(v), 2):
		s += v[j]
	print(s)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	grid = []
	for _ in range(n):
		row = [int(i) for i in input()]
		grid.append(row)
	islands = []
	found = set()
	from collections import deque

	def bfs(node):
		count = 0
		q = deque()
		q.append(node)
		found.add(node)
		dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		while q:
			(x, y) = q.popleft()
			count += 1
			for (dx, dy) in dirs:
				(newx, newy) = (x + dx, y + dy)
				if 0 <= newx < len(grid) and 0 <= newy < len(grid[0]):
					if (newx, newy) not in found and grid[newx][newy] == 1:
						q.append((newx, newy))
						found.add((newx, newy))
		return count
	for i in range(len(grid)):
		for j in range(len(grid[0])):
			if (i, j) not in found:
				if grid[i][j] == 1:
					ans = bfs((i, j))
					if ans > 0:
						islands.append(ans)
	islands = sorted(islands, reverse=True)
	p1 = 0
	p2 = 0
	i = 0
	while True:
		if i >= len(islands):
			break
		else:
			p1 += islands[i]
		i += 1
		if i >= len(islands):
			break
		else:
			p2 += islands[i]
		i += 1
	print(p2)


for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	G = []
	for i in range(n):
		G.append(input())
	F = {}
	A = []
	for j in range(n):
		for i in range(m):
			if G[j][i] == '1' and (not (i, j) in F):
				q = [(i, j)]
				s = {}
				while q:
					(x, y) = q.pop()
					if G[y][x] == '1' and (not (x, y) in s):
						s[x, y] = 1
						if x + 1 != m:
							q.append((x + 1, y))
						if x != 0:
							q.append((x - 1, y))
						if y + 1 != n:
							q.append((x, y + 1))
						if y != 0:
							q.append((x, y - 1))
				A.append(len(s))
				F.update(s)
	A.sort(reverse=True)
	print(sum(A[1::2]))


import sys

def inside(x, y, n, m):
	if x >= 0 and y >= 0 and (x < n) and (y < m):
		return True
	else:
		return False

def landsFill(matrix, n, m, *cord):
	dimen = [(0, 1), (0, -1), (1, 0), (-1, 0)]
	(i, j) = cord
	que = []
	matrix[i][j] = '0'
	que.append(cord)
	size = 0
	while len(que) != 0:
		tup = que[0]
		que.pop(0)
		size += 1
		for (p, q) in dimen:
			newp = p + tup[0]
			newq = q + tup[1]
			if inside(newp, newq, n, m) and matrix[newp][newq] == '1':
				matrix[newp][newq] = '0'
				que.append((newp, newq))
	return size
for _ in range(int(sys.stdin.readline())):
	matrix = []
	res = []
	(n, m) = map(int, sys.stdin.readline().split())
	for i in range(n):
		matrix.append(list(sys.stdin.readline()))
	for i in range(n):
		for j in range(m):
			if matrix[i][j] == '1':
				res.append(landsFill(matrix, n, m, i, j))
	res.sort(reverse=True)
	total = 0
	for u in range(1, len(res), 2):
		total += res[u]
	print(total)


from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

def sizes(world, i, j, n, m):
	size = 1
	world[i][j] = 0
	if j != 0 and world[i][j - 1] != 0:
		size += sizes(world, i, j - 1, n, m)
	if i != 0 and world[i - 1][j] != 0:
		size += sizes(world, i - 1, j, n, m)
	if j != m - 1 and world[i][j + 1] != 0:
		size += sizes(world, i, j + 1, n, m)
	if i != n - 1 and world[i + 1][j] != 0:
		size += sizes(world, i + 1, j, n, m)
	return size
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	world = [[int(land) for land in input()] for _ in range(n)]
	captured = []
	land_sizes = [sizes(world, i, j, n, m) for i in range(n) for j in range(m) if world[i][j] != 0]
	land_sizes.sort(reverse=True)
	print(0) if len(land_sizes) == 1 else print(sum(land_sizes[1::2]))


import sys
sys.setrecursionlimit(1000000)
from collections import defaultdict

def bfs(a, b, visited, arr):
	if a < 0 or b < 0 or a > n - 1 or (b > m - 1) or (arr[a][b] != '1') or (visited[a][b] == True):
		return 0
	else:
		visited[a][b] = True
		return bfs(a - 1, b, visited, arr) + bfs(a, b - 1, visited, arr) + bfs(a + 1, b, visited, arr) + bfs(a, b + 1, visited, arr) + 1
t = int(input())
for k in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(list(input()))
	visited = [[False for i in range(m)] for j in range(n)]
	ans = []
	for i in range(n):
		for j in range(m):
			if visited[i][j] == False and arr[i][j] != '0':
				ans.append(bfs(i, j, visited, arr))
	ans = sorted(ans, reverse=True)
	sum = 0
	for i in range(1, len(ans), 2):
		sum += ans[i]
	print(sum)


def solve(x, n, m):
	collections = {}
	to_be_allocated = 0
	y = [[-1] * m for i in range(n)]
	for i in range(n):
		for j in range(m):
			if x[i][j] == '1':
				left = -1
				top = -1
				if j != 0:
					left = y[i][j - 1]
				if i != 0:
					top = y[i - 1][j]
				if left == -1 and top == -1:
					y[i][j] = to_be_allocated
					collections[to_be_allocated] = {(i, j)}
					to_be_allocated += 1
				elif left == -1:
					y[i][j] = top
					collections[top].add((i, j))
				elif top == -1:
					y[i][j] = left
					collections[left].add((i, j))
				else:
					y[i][j] = left
					collections[left].add((i, j))
					if left != top:
						collections[left] = collections[left].union(collections[top])
						for point in collections[top]:
							y[point[0]][point[1]] = left
						collections[top] = set()
	count = []
	for val in collections.values():
		count.append(len(val))
	count.sort(reverse=True)
	count = count[1::2]
	return sum(count)
for q in range(int(input())):
	(n, m) = map(int, input().split())
	x = []
	for i in range(n):
		x.append(input())
	print(solve(x, n, m))


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(mat, visited, x, y):
	if x >= n or y >= m or x < 0 or (y < 0):
		return 0
	if mat[x][y] != '1':
		return 0
	if visited[x][y]:
		return 0
	visited[x][y] = True
	return dfs(mat, visited, x + 1, y) + dfs(mat, visited, x, y + 1) + dfs(mat, visited, x - 1, y) + dfs(mat, visited, x, y - 1) + 1
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mat = []
	for i in range(n):
		mat.append(list(input()))
	visited = [[False for i in range(m)] for j in range(n)]
	al = []
	for i in range(n):
		for j in range(m):
			if mat[i][j] == '0' or visited[i][j] == False:
				al.append(dfs(mat, visited, i, j))
	al.sort(reverse=True)
	ans = 0
	for i in range(1, len(al), 2):
		ans += al[i]
	print(ans)


from sys import setrecursionlimit
setrecursionlimit(100000)

def fun(li, i, j, count, n, m):
	if i >= 1 and j >= 0 and (j <= m - 1) and (i <= n - 1):
		if li[i - 1][j] == '1':
			li[i - 1][j] = '0'
			count[0] += 1
			fun(li, i - 1, j, count, n, m)
	if i <= n - 2 and i >= 0 and (j >= 0) and (j <= m - 1):
		if li[i + 1][j] == '1':
			li[i + 1][j] = '0'
			count[0] += 1
			fun(li, i + 1, j, count, n, m)
	if j >= 1 and j <= m - 1 and (i >= 0) and (i <= n - 1):
		if li[i][j - 1] == '1':
			li[i][j - 1] = '0'
			count[0] += 1
			fun(li, i, j - 1, count, n, m)
	if j <= m - 2 and j >= 0 and (i <= n - 1) and (i >= 0):
		if li[i][j + 1] == '1':
			li[i][j + 1] = '0'
			count[0] += 1
			fun(li, i, j + 1, count, n, m)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	li = []
	for __ in range(n):
		a = input()
		temp = [x for x in a]
		li.append(temp)
	conter = []
	for i in range(n):
		for j in range(m):
			count = [0]
			if li[i][j] == '1':
				li[i][j] = '0'
				count[0] = 1
				fun(li, i, j, count, n, m)
				conter.append(count[0])
	conter.sort(reverse=True)
	summ = 0
	for i in range(1, len(conter), 2):
		summ += conter[i]
	print(summ)


def check(i, j):
	if (i >= 0 and j >= 0) and (i < n and j < m):
		return True
	return False

def sizeof(i, j):
	d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
	q = [[i, j]]
	l[i][j] = '0'
	size = 0
	while q:
		size += 1
		a = q.pop(0)
		for (x, y) in d:
			if check(a[0] + x, a[1] + y):
				if l[a[0] + x][a[1] + y] == '1':
					l[a[0] + x][a[1] + y] = '0'
					q.append([a[0] + x, a[1] + y])
	return size
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = [list(input()) for i in range(n)]
	s1 = []
	for i in range(n):
		for j in range(m):
			if l[i][j] == '1':
				sz = sizeof(i, j)
				s1.append(sz)
	s1.sort(reverse=True)
	sum = 0
	for i in range(1, len(s1), 2):
		sum += s1[i]
	print(sum)


def check(p, q, pl, ql):
	if p > -1 and p < pl and (q > -1) and (q < ql):
		return True
	return False
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [list(map(int, list(input()))) for i in range(n)]
	ans = []
	tt = [(-1, 0), (0, -1), (1, 0), (0, 1)]
	for i in range(n):
		for j in range(m):
			if check(i, j, n, m) and a[i][j] == 1:
				que = [(i, j)]
				count = 0
				while que:
					pos = que.pop(0)
					(x, y) = (pos[0], pos[1])
					if check(x, y, n, m) and a[x][y] == 1:
						count += 1
						a[x][y] = 2
						for k in tt:
							(v1, v2) = (x + k[0], y + k[1])
							if check(v1, v2, n, m) and a[v1][v2] == 1:
								que.append((v1, v2))
				ans.append(count)
	ans.sort()
	ans = ans[::-1]
	nn = len(ans)
	fans = 0
	for i in range(1, nn, 2):
		fans += ans[i]
	print(fans)


def check(i, j):
	if i >= 0 and j >= 0 and (i < n) and (j < m):
		return True
	else:
		return False

def findsize(i, j):
	d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
	q = [[i, j]]
	l[i][j] = '0'
	size = 0
	while q:
		size += 1
		a = q.pop(0)
		for (x, y) in d:
			if check(a[0] + x, a[1] + y):
				if l[a[0] + x][a[1] + y] == '1':
					l[a[0] + x][a[1] + y] = '0'
					q.append([a[0] + x, a[1] + y])
	return size
t = int(input())
for i in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	l = []
	s1 = []
	for j in range(n):
		s = list(input())
		l.append(s)
	for x in range(n):
		for y in range(m):
			if l[x][y] == '1':
				sz = findsize(x, y)
				s1.append(sz)
	s1.sort(reverse=True)
	sum1 = 0
	for j in range(1, len(s1), 2):
		sum1 += s1[j]
	print(sum1)


def Solve(l, x, y):
	vis = set()
	queue = [(x, y)]
	d = 0
	while queue:
		(px, py) = queue.pop(0)
		if px < 0 or py < 0 or px >= r or (py >= c) or ((px, py) in vis) or (l[px][py] == 0):
			continue
		vis.add((x, y))
		l[px][py] = 0
		d += 1
		queue.append((px + 1, py))
		queue.append((px - 1, py))
		queue.append((px, py + 1))
		queue.append((px, py - 1))
	return d
for _ in range(int(input())):
	(r, c) = map(int, input().split())
	l = []
	for x in range(r):
		l.append(list(map(int, list(input()))))
	rs = []
	for x in range(r):
		for y in range(c):
			if l[x][y] == 1:
				rs += [Solve(l, x, y)]
	rs.sort(reverse=True)
	print(sum(rs[1::2]))


import sys
sys.setrecursionlimit(150000)

def left(l, a, b):
	if b == 0:
		return False
	elif l[a][b - 1] == '1':
		return True
	else:
		return False

def right(l, a, b):
	if b == len(l[0]) - 1:
		return False
	elif l[a][b + 1] == '1':
		return True
	else:
		return False

def top(l, a, b):
	if a == 0:
		return False
	elif l[a - 1][b] == '1':
		return True
	else:
		return False

def down(l, a, b):
	if a == len(l) - 1:
		return False
	elif l[a + 1][b] == '1':
		return True
	else:
		return False

def score(cl, l, a, b):
	scr = 0
	if (a, b) in cl:
		return 0
	cl.add((a, b))
	l[a][b] = '0'
	if right(l, a, b):
		scr += 1 + score(cl, l, a, b + 1)
	if left(l, a, b):
		scr += 1 + score(cl, l, a, b - 1)
	if top(l, a, b):
		scr += 1 + score(cl, l, a - 1, b)
	if down(l, a, b):
		scr += 1 + score(cl, l, a + 1, b)
	return scr
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	scl = []
	l = []
	cl = set()
	for i in range(n):
		l.append(list(input()))
	k = 0
	for i in range(len(l)):
		for j in range(len(l[0])):
			if l[i][j] == '1':
				scl.append(1 + score(cl, l, i, j))
	scr1 = 0
	scl.sort()
	scl.reverse()
	scl = scl[1::2]
	if scl is None:
		print(1)
		continue
	for sr in scl:
		scr1 += sr
	print(scr1)


from sys import setrecursionlimit
setrecursionlimit(100000)

def get_connected_components(arr):

	def dfs(arr, i, j, n):
		n += 1
		arr[i][j] = '0'
		for (p, q) in [(i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)]:
			if 0 <= p < len(arr) and 0 <= q < len(arr[0]) and (arr[p][q] == '1'):
				n = dfs(arr, p, q, n)
		return n
	l = []
	for i in range(len(arr)):
		for j in range(len(arr[0])):
			if arr[i][j] == '1':
				no = dfs(arr, i, j, 0)
				l.append(no)
	return l
for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	arr = []
	for _ in range(n):
		row = list(input())
		arr.append(row)
	connected_components = get_connected_components(arr)
	connected_components.sort(reverse=True)
	print(sum(connected_components[1::2]))


from collections import deque
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	grid = []
	for _ in range(N):
		s = list(map(int, input()))
		grid.append(s)
	queue = deque()
	result = []
	visited = set()
	for i in range(N):
		for j in range(M):
			if grid[i][j] == 1:
				queue.append((i, j))
				grid[i][j] = 0
				ans = 0
				while queue:
					x = queue.popleft()
					ans += 1
					if x not in visited:
						visited.add(x)
						if x[1] + 1 < M:
							if grid[x[0]][x[1] + 1] == 1:
								queue.append((x[0], x[1] + 1))
								grid[x[0]][x[1] + 1] = 0
						if x[1] - 1 >= 0:
							if grid[x[0]][x[1] - 1] == 1:
								queue.append((x[0], x[1] - 1))
								grid[x[0]][x[1] - 1] = 0
						if x[0] + 1 < N:
							if grid[x[0] + 1][x[1]] == 1:
								queue.append((x[0] + 1, x[1]))
								grid[x[0] + 1][x[1]] = 0
						if x[0] - 1 >= 0:
							if grid[x[0] - 1][x[1]] == 1:
								queue.append((x[0] - 1, x[1]))
								grid[x[0] - 1][x[1]] = 0
				result.append(ans)
	result.sort(reverse=True)
	k = 1
	score = 0
	while k < len(result):
		score += result[k]
		k += 2
	print(score)


import sys
sys.setrecursionlimit(10 ** 6)

def check(arr, i, j, count):
	if min(i, j) < 0 or i >= n or j >= m:
		return count
	elif arr[i][j] == '0':
		return count
	else:
		count += 1
		arr[i][j] = '0'
		count = check(arr, i - 1, j, count)
		count = check(arr, i, j - 1, count)
		count = check(arr, i + 1, j, count)
		count = check(arr, i, j + 1, count)
		return count
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	re = []
	arr = []
	for i in range(n):
		a = list(input())
		arr.append(a)
	for i in range(n):
		for j in range(m):
			count = 0
			re.append(check(arr, i, j, count))
	re.sort()
	re = re[::-1]
	chef = 0
	for i in range(len(re)):
		if i & 1:
			chef += re[i]
	print(chef)


def find_chains(l, i, j, r, c):
	queue = [(i, j)]
	vis = set()
	d = 0
	while queue:
		(x, y) = queue.pop()
		if x < 0 or y < 0 or x >= r or (y >= c) or ((x, y) in vis) or (l[x][y] == 0):
			continue
		vis.add((i, j))
		l[x][y] = 0
		d += 1
		queue.append((x + 1, y))
		queue.append((x, y + 1))
		queue.append((x - 1, y))
		queue.append((x, y - 1))
	return d
try:
	t = int(input())
	while t:
		l = []
		(r, c) = map(int, input().split())
		for i in range(r):
			l.append(list(map(int, input())))
		max_size = []
		for i in range(r):
			for j in range(c):
				if l[i][j] == 1:
					max_size += [find_chains(l, i, j, r, c)]
		max_size.sort(reverse=True)
		print(sum(max_size[1::2]))
except:
	pass


import sys
sys.setrecursionlimit(10 ** 5)

def noOfConnectedLands(row, col, matrix, visited, N, M):
	if row >= N or row < 0 or col >= M or (col < 0):
		return 0
	if matrix[row][col] == '0':
		return 0
	if matrix[row][col] == '1' and visited[row][col] == False:
		visited[row][col] = True
		return 1 + noOfConnectedLands(row + 1, col, matrix, visited, N, M) + noOfConnectedLands(row - 1, col, matrix, visited, N, M) + noOfConnectedLands(row, col + 1, matrix, visited, N, M) + noOfConnectedLands(row, col - 1, matrix, visited, N, M)
	return 0
testcases = int(input().strip())
for testcase in range(testcases):
	(N, M) = map(int, input().strip().split())
	matrix = []
	visited = []
	for i in range(N):
		row = input().strip()
		matrix.append(row)
		visited.append([False for x in range(M)])
	arr = []
	for i in range(N):
		for j in range(M):
			if not visited[i][j] and matrix[i][j] == '1':
				x = noOfConnectedLands(i, j, matrix, visited, N, M)
				arr.append(x)
	arr = sorted(arr)[::-1]
	if len(arr) > 1:
		print(sum(arr[1::2]))
	else:
		print(0)


from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

def b_t(i, j):
	if i < 0:
		return 0
	if j < 0:
		return 0
	if i >= n:
		return 0
	if j >= m:
		return 0
	if visited[i][j]:
		return 0
	visited[i][j] = True
	return b_t(i - 1, j) + b_t(i, j - 1) + b_t(i + 1, j) + b_t(i, j + 1) + 1

def answer():
	for i in range(n):
		for j in range(m):
			if a[i][j] == '0':
				visited[i][j] = True
	val = []
	for i in range(n):
		for j in range(m):
			if not visited[i][j]:
				val.append(b_t(i, j))
	val.sort(reverse=True)
	ans = 0
	for i in range(1, len(val), 2):
		ans += val[i]
	return ans
for T in range(int(input())):
	(n, m) = map(int, input().split())
	a = [input() for i in range(n)]
	visited = [[False for i in range(m)] for j in range(n)]
	print(answer())


try:
	import sys
	sys.setrecursionlimit(1000000)

	def dfs(i, j):
		count[0] += 1
		vis[i][j] = True
		for (x, y) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
			if x >= 0 and y >= 0 and (x < n) and (y < m) and (arr[x][y] == 1) and (vis[x][y] == False):
				dfs(x, y)
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		arr = []
		for i in range(n):
			arr.append(list(map(int, input())))
		a = []
		vis = [[False for i in range(m)] for j in range(n)]
		for i in range(n):
			for j in range(m):
				if arr[i][j] == 1 and vis[i][j] == False:
					count = [0]
					dfs(i, j)
					a.append(count[0])
		a.sort(reverse=True)
		ans = 0
		for i in range(1, len(a), 2):
			ans += a[i]
		print(ans)
except:
	pass


import sys
sys.setrecursionlimit(10 ** 7)

class Graph:

	def __init__(self, n, m, g):
		self.n = n
		self.m = m
		self.g = g
		self.sizes = []
		self.c = 0

	def dfs(self, i, j, visited):
		visited[i][j] = True
		if self.g[i][j] == '0' or self.g[i][j] == '2':
			return
		self.g[i][j] = '2'
		self.c += 1
		if j - 1 >= 0 and visited[i][j - 1] == False:
			self.dfs(i, j - 1, visited)
		if i - 1 >= 0 and visited[i - 1][j] == False:
			self.dfs(i - 1, j, visited)
		if i + 1 < self.n and j < self.m and (visited[i + 1][j] == False):
			self.dfs(i + 1, j, visited)
		if j + 1 < self.m and i < self.n and (visited[i][j + 1] == False):
			self.dfs(i, j + 1, visited)

	def countIslandSizes(self):
		visited = [[False for j in range(self.m)] for i in range(self.n)]
		for i in range(self.n):
			for j in range(self.m):
				if visited[i][j] == False and self.g[i][j] == '1':
					self.c = 0
					self.dfs(i, j, visited)
					self.sizes.append(self.c)
		return self.sizes
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	graph = [[] for i in range(n)]
	for i in range(n):
		graph[i] = list(input())
	g = Graph(n, m, graph)
	x = sorted(g.countIslandSizes(), reverse=True)
	p = 0
	for i in range(1, len(x), 2):
		p += x[i]
	print(p)


from collections import deque
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	Map = []
	for i in range(n):
		Map.append(list(input()))
	pairs = [(1, 0), (-1, 0), (0, -1), (0, 1)]
	lands = []

	def inside(x, y):
		return x >= 0 and y >= 0 and (x < n) and (y < m)

	def bfs(i, j):
		q = deque()
		Map[i][j] = '0'
		q.append((i, j))
		res = 0
		while q:
			(x, y) = q.popleft()
			res += 1
			for (dx, dy) in pairs:
				xx = x + dx
				yy = y + dy
				if inside(xx, yy) and Map[xx][yy] == '1':
					Map[xx][yy] = '0'
					q.append((xx, yy))
		return res
	for i in range(n):
		for j in range(m):
			if Map[i][j] == '1':
				lands.append(bfs(i, j))
	lands.sort(reverse=True)
	chef = 0
	for i in range(1, len(lands), 2):
		chef += lands[i]
	print(chef)


def solve():
	(n, m) = map(int, input().split())
	visited = [[False for i in range(m)] for j in range(n)]
	(a, ans) = ([], [])
	for i in range(n):
		a.append(list(input().strip()))

	def check(x, y):
		if x < 0 or x >= n or y < 0 or (y >= m):
			return False
		if visited[x][y] or a[x][y] == '0':
			return False
		return True

	def bfs(i, j):
		q = [(i, j)]
		visited[i][j] = True
		c = 0
		while len(q) != 0:
			p = q.pop(0)
			c += 1
			if check(p[0] + 1, p[1]):
				visited[p[0] + 1][p[1]] = True
				q.append((p[0] + 1, p[1]))
			if check(p[0] - 1, p[1]):
				visited[p[0] - 1][p[1]] = True
				q.append((p[0] - 1, p[1]))
			if check(p[0], p[1] + 1):
				visited[p[0]][p[1] + 1] = True
				q.append((p[0], p[1] + 1))
			if check(p[0], p[1] - 1):
				visited[p[0]][p[1] - 1] = True
				q.append((p[0], p[1] - 1))
		return c
	for i in range(n):
		for j in range(m):
			if a[i][j] == '1' and (not visited[i][j]):
				ans.append(bfs(i, j))
	ans.sort(reverse=True)
	score = 0
	for i in range(1, len(ans), 2):
		score += ans[i]
	print(score)
for _ in range(int(input())):
	solve()


import numpy as np
testcase = int(input())
for t in range(testcase):
	[N, M] = list(map(int, input().split(' ')))
	mat = np.zeros([N + 2, M + 2])
	for i in range(N):
		mat[i + 1][1:M + 1] = list(input())
	R = np.zeros([N + 2, M + 2])
	k = 1
	for i in range(1, N + 1):
		for j in range(1, M + 1):
			if mat[i, j] == 1:
				if mat[i - 1, j] == 0 and mat[i, j - 1] == 0:
					R[i, j] = k
					k += 1
				elif mat[i - 1, j] == 1 and mat[i, j - 1] == 0:
					R[i, j] = R[i - 1, j]
				elif mat[i - 1, j] == 0 and mat[i, j - 1] == 1:
					R[i, j] = R[i, j - 1]
				elif mat[i - 1, j] == 1 and mat[i, j - 1] == 1:
					R[i, j] = R[i - 1, j]
					if R[i - 1, j] != R[i, j - 1]:
						R[R == R[i, j - 1]] = R[i - 1, j]
	klist = np.zeros(k)
	for i in R:
		for j in i:
			if int(j) != 0:
				klist[int(j)] += 1
	klist = np.array(sorted(klist, reverse=True))
	klist = klist[klist > 0]
	sum1 = 0
	for p in range(0, len(klist)):
		if p % 2 != 0:
			sum1 = sum1 + klist[p]
	print(int(sum1))


def valid(a, b, visited, A, N, M):
	if a >= N or a < 0 or b >= M or (b < 0):
		return False
	if visited[a][b] or A[a][b] == '0':
		return False
	return True

def dfs(x, y, visited, A, N, M):
	visited[x][y] = 1
	stack = [[x, y]]
	dx = [-1, 0, 1, 0]
	dy = [0, 1, 0, -1]
	c = 1
	while stack:
		node = stack.pop()
		x = node[0]
		y = node[1]
		for i in range(4):
			if valid(x + dx[i], y + dy[i], visited, A, N, M) == True:
				c = c + 1
				stack.append([x + dx[i], y + dy[i]])
				visited[x + dx[i]][y + dy[i]] = True
	return c

def find(A, N, M):
	visited = [[0 for i in range(M)] for j in range(N)]
	c = 0
	ans = []
	for i in range(N):
		for j in range(M):
			if A[i][j] == '1' and visited[i][j] == 0:
				ans.append(dfs(i, j, visited, A, N, M))
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		k = list(input())
		l.append(k)
	ans = find(l, n, m)
	ans.sort(reverse=True)
	res = 0
	for i in range(1, len(ans), 2):
		res = res + ans[i]
	print(res)


def solve(i, j):
	if i >= 0 and i < n and (j >= 0) and (j < m):
		if a[i][j] == 1 and vis[i][j] == 0:
			vis[i][j] = 1
			x = [-1, 0, 1, 0]
			y = [0, 1, 0, -1]
			sm = 1
			for k in range(4):
				sm += solve(i + x[k], j + y[k])
			return sm
	return 0
import sys
sys.setrecursionlimit(10 ** 6)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [[0 for j in range(m)] for i in range(n)]
	vis = [[0 for j in range(m)] for i in range(n)]
	for i in range(n):
		s = input()
		for j in range(m):
			a[i][j] = int(s[j])
	res = []
	for i in range(n):
		for j in range(m):
			if a[i][j] == 1 and vis[i][j] == 0:
				t = solve(i, j)
				res.append(t)
	res.sort(reverse=True)
	ans = 0
	for i in range(len(res)):
		if i & 1:
			ans += res[i]
	print(ans)


import sys
sys.setrecursionlimit(1000000)

def godir(world, i, j, n, m):
	size = 0
	if world[i][j] == '1':
		size += 1
		world[i][j] = '0'
		if i != n - 1:
			size += godir(world, i + 1, j, n, m)
		if j != m - 1:
			size += godir(world, i, j + 1, n, m)
		if i != 0:
			size += godir(world, i - 1, j, n, m)
		if j != 0:
			size += godir(world, i, j - 1, n, m)
	return size

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = tuple(map(int, input().split()))
		world = []
		for r in range(n):
			world.append(list(input()))
		(sizes, l) = ([], 0)
		for r in range(n):
			for c in range(m):
				if world[r][c] == '1':
					size = 1
					world[r][c] = '0'
					if r != n - 1:
						size += godir(world, r + 1, c, n, m)
					if c != m - 1:
						size += godir(world, r, c + 1, n, m)
					sizes += [size]
					l += 1
		sizes.sort()
		sizes = sizes[::-1]
		print(sum(sizes[1::2]))
	return 0
main()


import sys
sys.setrecursionlimit(100000)

def dfs(matrix, i, j, m, n):
	if i < 0 or i >= m or j < 0 or (j >= n):
		return 0
	if matrix[i][j] != '1':
		return 0
	matrix[i][j] = '2'
	ans = 1
	for (x, y) in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
		ans += dfs(matrix, i + x, j + y, m, n)
	return ans
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	matrix = []
	for __ in range(m):
		row = list(input())
		matrix.append(row)
	l = []
	(m, n) = (len(matrix), len(matrix[0]))
	for i in range(len(matrix)):
		for j in range(len(matrix[0])):
			if matrix[i][j] == '1':
				k = dfs(matrix, i, j, m, n)
				l.append(k)
	l.sort()
	(chef, mike) = (0, 0)
	turn = 1
	for term in range(len(l) - 1, -1, -1):
		if turn == 1:
			mike += l[term]
			turn ^= 1
		else:
			chef += l[term]
			turn ^= 1
	print(chef)


from sys import setrecursionlimit
setrecursionlimit(100000)

def floodfill(i, j):
	if i >= row:
		return 0
	if j >= col:
		return 0
	if array[i][j] == 0:
		return 0
	if i < 0:
		return 0
	if j < 0:
		return 0
	array[i][j] = 0
	return 1 + (floodfill(i + 1, j) + floodfill(i - 1, j) + floodfill(i, j + 1) + floodfill(i, j - 1))

def fun(row, col):
	new_array = []
	for i in range(row):
		for j in range(col):
			a = floodfill(i, j)
			if a != 0:
				new_array.append(a)
	new_array.sort()
	new_array = new_array[::-1]
	summing = 0
	for i in range(1, len(new_array), 2):
		summing += new_array[i]
	return summing
for test in range(int(input())):
	(row, col) = list(map(int, input().split()))
	array = []
	for i in range(row):
		array.append(list(map(int, list(input()))))
	print(fun(row, col))


t = int(input())

def dfs(i, j, comp, visited, grid):
	max_j = len(grid[0]) - 1
	max_i = len(grid) - 1
	stack = [(i, j)]
	while len(stack):
		(x, y) = stack.pop()
		if grid[x][y] == '0':
			visited[x][y] = True
		elif not visited[x][y]:
			comp[0] += 1
			visited[x][y] = True
			left = (x, max(0, y - 1))
			right = (x, min(max_j, y + 1))
			bottom = (min(max_i, x + 1), y)
			top = (max(0, x - 1), y)
			stack += [top, bottom, left, right]
for _ in range(t):
	(n, m) = map(int, input().split())
	grid = [input() for _ in range(n)]
	visited = [[False] * m for _ in range(n)]
	components = []
	for i in range(n):
		for j in range(m):
			if grid[i][j] == '0':
				visited[i][j] = True
			elif grid[i][j] == '1':
				if not visited[i][j]:
					comp = [0]
					dfs(i, j, comp, visited, grid)
					components.append(comp[0])
					comp[0] = 0
	components.sort(reverse=True)
	print(sum([c for (i, c) in enumerate(components) if i & 1 == 1]))


from queue import Queue
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	matrix = [['0' for i in range(m + 2)]]
	for i in range(n):
		matrix.append(list(input()))
		matrix[-1].append('0')
		matrix[-1].insert(0, '0')
	matrix.append(['0' for i in range(m + 2)])
	queue = Queue()
	bfs_op = []
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if matrix[i][j] == '1':
				queue.put([i, j])
				l = []
				while not queue.empty():
					u = queue.get()
					l.append(u)
					matrix[u[0]][u[1]] = 'visited'
					if matrix[u[0]][u[1] + 1] == '1':
						queue.put([u[0], u[1] + 1])
						matrix[u[0]][u[1] + 1] = 'visited'
					if matrix[u[0]][u[1] - 1] == '1':
						queue.put([u[0], u[1] - 1])
						matrix[u[0]][u[1] - 1] = 'visited'
					if matrix[u[0] + 1][u[1]] == '1':
						queue.put([u[0] + 1, u[1]])
						matrix[u[0] + 1][u[1]] = 'visited'
					if matrix[u[0] - 1][u[1]] == '1':
						queue.put([u[0] - 1, u[1]])
						matrix[u[0] - 1][u[1]] = 'visited'
				bfs_op.append(len(l))
	bfs_op.sort(reverse=True)
	s = 0
	i = 1
	while i < len(bfs_op):
		s += bfs_op[i]
		i += 2
	print(s)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lis = []
	for _ in range(n):
		lis.append([int(x) for x in input()])
	cnt = []
	for i in range(n):
		for j in range(m):
			count = 0
			if lis[i][j] == 1:
				lis[i][j] = 0
				count += 1
				q = []
				q.append((i, j))
				while len(q) > 0:
					t = q.pop(0)
					if t[0] < n - 1:
						if lis[t[0] + 1][t[1]] == 1:
							count += 1
							lis[t[0] + 1][t[1]] = 0
							q.append((t[0] + 1, t[1]))
					if t[1] < m - 1:
						if lis[t[0]][t[1] + 1] == 1:
							count += 1
							lis[t[0]][t[1] + 1] = 0
							q.append((t[0], t[1] + 1))
					if t[0] > 0:
						if lis[t[0] - 1][t[1]] == 1:
							count += 1
							lis[t[0] - 1][t[1]] = 0
							q.append((t[0] - 1, t[1]))
					if t[1] > 0:
						if lis[t[0]][t[1] - 1] == 1:
							count += 1
							lis[t[0]][t[1] - 1] = 0
							q.append((t[0], t[1] - 1))
				cnt.append(count)
	cnt.sort(reverse=True)
	if len(cnt) == 1 or len(cnt) == 0:
		print(0)
	else:
		ans_lis = cnt[1::2]
		ans = sum(ans_lis)
		print(ans)