There is a field with plants — a grid with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$); out of its $NM$ cells, $K$ cells contain plants, while the rest contain weeds. Two cells are adjacent if they have a common side.
You want to build fences in the field in such a way that the following conditions hold for each cell that contains a plant:
- it is possible to move from this cell to each adjacent cell containing a plant without crossing any fences
- it is impossible to move from this cell to any cell containing weeds or to leave the grid without crossing any fences
The fences can only be built between cells or on the boundary of the grid, i.e. on the sides of cells. The total length of the built fences is the number of pairs of side-adjacent cells such that there is a fence built on their common side plus the number of sides of cells on the boundary of the grid which have fences built on them. Find the minimum required total length of fences that need to be built.

-----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 three space-separated integers $N$, $M$ and $K$.
- $K$ lines follow. Each of these lines contains two space-separated integers $r$ and $c$ denoting that the cell in row $r$ and column $c$ contains a plant.

-----Output-----
For each test case, print a single line containing one integer — the minimum required length of fences.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N, M \le 10^9$
- $1 \le K \le 10^5$
- $1 \le r \le N$
- $1 \le c \le M$
- the cells containing plants are pairwise distinct

-----Subtasks-----
Subtask #1 (30 points): $1 \le N, M \le 1,000$
Subtask #2 (70 points): original constraints

-----Example Input-----
2
4 4 9
1 4
2 1 
2 2
2 3
3 1
3 3
4 1
4 2
4 3
4 4 1
1 1

-----Example Output-----
20
4

-----Explanation-----
Example case 1: The field looks like this ('x' denotes a cell containing a plant, '.' denotes a cell containing weeds):
...x
xxx.
x.x.
xxx.

An optimal solution is to build fences around the topmost plant (with length $4$), around the remaining eight plants (with length $12$) and around the hole between them (with length $4$). The total length is $4+12+4 = 20$.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split()))
	d = {}
	s = 0
	for i in range(k):
		(x, y) = list(map(int, input().split()))
		d[x, y] = 1
		s -= d.get((x - 1, y), -1)
		s -= d.get((x, y - 1), -1)
		s -= d.get((x, y + 1), -1)
		s -= d.get((x + 1, y), -1)
	print(s)


t = int(input())
while t != 0:
	(n, m, k) = [int(x) for x in input().split()]
	ans = 4 * k
	A = {}
	while k != 0:
		(x, y) = [int(x) for x in input().split()]
		A[x, y] = 1
		if A.get((x + 1, y)) == 1:
			ans = ans - 2
		if A.get((x, y + 1)) == 1:
			ans = ans - 2
		if A.get((x - 1, y)) == 1:
			ans = ans - 2
		if A.get((x, y - 1)) == 1:
			ans = ans - 2
		k = k - 1
	print(ans)
	t = t - 1


def main():
	for _ in range(int(input())):
		(n, m, k) = map(int, input().split())
		plants = dict()
		ans = 0
		while k != 0:
			(r, c) = map(int, input().split())
			plants[r, c] = True
			ans += 4
			if plants.get((r + 1, c), False):
				ans -= 2
			if plants.get((r - 1, c), False):
				ans -= 2
			if plants.get((r, c + 1), False):
				ans -= 2
			if plants.get((r, c - 1), False):
				ans -= 2
			k -= 1
		print(ans)
main()


t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	res = k * 4
	c = 0
	list1 = set()
	for i in range(k):
		(p, q) = map(int, input().split())
		list1.add((p, q))
	for (p, q) in list1:
		if p != 1 and q != 1:
			if (p - 1, q) in list1:
				c += 1
			if (p, q - 1) in list1:
				c += 1
		elif p == 1:
			if (p, q - 1) in list1:
				c += 1
		elif q == 1:
			if (p - 1, q) in list1:
				c += 1
	res -= 2 * c
	print(res)


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	d = defaultdict(list)
	for i in range(k):
		(r, c) = map(int, input().split())
		d[r].append(c)
	total = 0
	for (i, j) in d.items():
		for k in j:
			if k - 1 not in j:
				total += 1
			if k + 1 not in j:
				total += 1
			if i == 1 or i - 1 not in d or k not in d[i - 1]:
				total += 1
			if i == n or i + 1 not in d or k not in d[i + 1]:
				total += 1
	print(total)


def answer():
	value = 0
	for x in d.keys():
		(i, j) = (x[0], x[1])
		if (i, j + 1) in d.keys():
			value += 1
		if (i + 1, j) in d.keys():
			value += 1
		if (i - 1, j) in d.keys():
			value += 1
		if (i, j - 1) in d.keys():
			value += 1
	return 4 * k - value
for T in range(int(input())):
	(n, m, k) = map(int, input().split())
	d = dict()
	for i in range(k):
		(x, y) = map(int, input().split())
		d[x, y] = 1
	print(answer())


def fence(n, m, k, coords):
	dirs = [(0, -1), (0, 1), (1, 0), (-1, 0)]
	f = 0
	for coord in coords:
		for (dx, dy) in dirs:
			(x, y) = (coord[0] + dx, coord[1] + dy)
			if x >= 0 and x < n and (y >= 0) and (y < m) and ((x, y) in coords):
				pass
			else:
				f += 1
	return f
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	L = []
	for _ in range(k):
		(a, b) = map(int, input().split())
		L.append((a - 1, b - 1))
	coords = set(L)
	print(fence(n, m, k, coords))


from sys import stdin

def sin():
	return stdin.readline()
for _ in range(int(sin())):
	(n, m, k) = list(map(int, sin().split()))
	d = {}
	ans = 4 * k
	for i in range(k):
		(r, c) = list(map(int, sin().split()))
		ans -= 2 * d.get((r - 1, c), 0) + 2 * d.get((r, c - 1), 0) + 2 * d.get((r + 1, c), 0) + 2 * d.get((r, c + 1), 0)
		d[r, c] = 1
	print(ans)


for _ in range(int(input())):
	(n, m, q) = map(int, input().split())
	p = []
	dic = {}
	for i in range(q):
		(x, y) = map(int, input().split())
		p.append([x, y])
		dic[x, y] = 1
	cnt = 0
	for u in p:
		r1 = u[0]
		r2 = u[1]
		one = (r1 - 1, r2)
		two = (r1 + 1, r2)
		thr = (r1, r2 - 1)
		fo = (r1, r2 + 1)
		s = 0
		if one in dic:
			s = s + 1
		if two in dic:
			s = s + 1
		if thr in dic:
			s = s + 1
		if fo in dic:
			s = s + 1
		re = 4 - s
		cnt = cnt + re
	print(cnt)


t = int(input())
while t:
	t -= 1
	d = {}
	(n, m, k) = [int(x) for x in list(input().split())]
	sum = 0
	while k:
		k -= 1
		(x, y) = [int(x) for x in list(input().split())]
		a = [-1, 1, 0, 0]
		b = [0, 0, -1, 1]
		for i in range(4):
			if (x + a[i], y + b[i]) in d:
				sum -= 1
			else:
				sum += 1
		d[x, y] = 1
	print(sum)


from collections import Counter
T = int(input())
for i in range(T):
	(N, M, K) = map(int, input().split())
	field = Counter()
	for j in range(K):
		(r, c) = map(int, input().split())
		field[r - 1, c - 1] = 1
	a = 0
	for pos in field:
		(j, k) = pos
		if field[j, k] == 1:
			if j + 1 < N and field[j + 1, k] == 1:
				a += 1
			if j > 0 and field[j - 1, k] == 1:
				a += 1
			if k + 1 < M and field[j, k + 1] == 1:
				a += 1
			if k > 0 and field[j, k - 1] == 1:
				a += 1
	print(K * 4 - a)


query = int(input())
for q in range(0, query):
	inp = list(map(int, input().split(' ')))
	n = inp[0]
	m = inp[1]
	k = inp[2]
	mp = {}
	ans = 0
	dx = [1, 0, -1, 0]
	dy = [0, 1, 0, -1]
	for i in range(0, k):
		XY = list(map(int, input().split(' ')[:2]))
		x = XY[0]
		y = XY[1]
		for j in range(0, 4):
			newX = x + dx[j]
			newY = y + dy[j]
			if newX in mp and newY in mp[newX] and (mp[newX][newY] > 0):
				ans = ans - 1
			else:
				ans = ans + 1
		if x not in mp:
			mp[x] = {}
			mp[x][y] = 1
		else:
			mp[x][y] = 1
	print(ans)


import numpy as np
t = int(input())
while t:
	t -= 1
	(n, m, k) = [int(x) for x in list(input().split())]
	l = np.array([['.'] * m] * n)
	while k:
		k -= 1
		(x, y) = [int(x) for x in list(input().split())]
		l[x - 1][y - 1] = 'X'
	sum = 0
	for i in range(n):
		for j in range(m):
			if l[i][j] == 'X':
				if i == 0 or l[i - 1][j] == '.':
					sum += 1
				if i == n - 1 or l[i + 1][j] == '.':
					sum += 1
				if j == 0 or l[i][j - 1] == '.':
					sum += 1
				if j == m - 1 or l[i][j + 1] == '.':
					sum += 1
	print(sum)


def find_fence(fencing, plants, height, width):
	setted_keys = set(plants.keys())
	for i in setted_keys:
		for j in plants[i]:
			if j - 1 in plants[i]:
				fencing -= 2
			if i + 1 in setted_keys and j in plants[i + 1]:
				fencing -= 2
	return fencing
a = int(input().strip())
for i in range(0, a):
	b = [int(x) for x in input().strip().split(' ')]
	plants = {}
	fencing = 0
	for j in range(0, b[2]):
		a = [int(x) for x in input().strip().split(' ')]
		if a[0] not in plants:
			plants[a[0]] = {a[1]}
		else:
			plants[a[0]].add(a[1])
		fencing += 4
	print(find_fence(fencing, plants, b[0], b[1]))


for _ in range(int(input())):
	(p, q, s) = map(int, input().split())
	m = dict()
	count = 0
	for _ in range(s):
		(r, c) = map(int, input().split())
		m[r, c] = 'x'
		if (r, c - 1) in m:
			count += 2
		if (r - 1, c) in m:
			count += 2
		if (r, c + 1) in m:
			count += 2
		if (r + 1, c) in m:
			count += 2
	print(s * 4 - count)


for tc in range(int(input())):
	(n, m, k) = map(int, input().split())
	res = k * 4
	count = 0
	list1 = set()
	for tc in range(k):
		(x, y) = map(int, input().split())
		list1.add((x, y))
	for (x, y) in list1:
		if x != 1 and y != 1:
			if (x - 1, y) in list1:
				count += 1
			if (x, y - 1) in list1:
				count += 1
		elif x == 1:
			if (x, y - 1) in list1:
				count += 1
		elif y == 1:
			if (x - 1, y) in list1:
				count += 1
	res -= 2 * count
	print(res)


t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().strip().split())
	plants = []
	stat = {}
	count = 0
	for i in range(k):
		(x, y) = map(int, input().strip().split())
		ele = (x, y)
		stat[ele] = 1
		plants.append([x, y])
		count += 4
		if stat.get((x - 1, y)) == 1:
			count -= 2
		if stat.get((x, y + 1)) == 1:
			count -= 2
		if stat.get((x + 1, y)) == 1:
			count -= 2
		if stat.get((x, y - 1)) == 1:
			count -= 2
	print(count)


from bisect import bisect_left, bisect_right
from heapq import heapify, heappush, heappop
from cmath import pi
from distutils import extension
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

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

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 a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

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
for _ in range(ii()):
	(n, m, k) = il()
	ans = 4 * k
	s = set()
	plants = []
	for l in range(k):
		(r, c) = il()
		s.add(str(r) + '@' + str(c))
		plants.append([r, c])
	dx = [-1, 1, 0, 0]
	dy = [0, 0, -1, 1]
	for p in plants:
		for c in range(4):
			if str(dx[c] + p[0]) + '@' + str(dy[c] + p[1]) in s:
				ans = ans - 1
	print(ans)


t = int(input())
for z in range(t):
	(n, m, k) = map(int, input().split())
	dict1 = {}
	for q in range(k):
		(r, c) = map(int, input().split())
		dict1[r, c] = [r, c]
	s = 0
	for i in dict1.keys():
		lst = list(i)
		rr = lst[0]
		cc = lst[1]
		tp = (rr, cc)
		if (rr, cc + 1) not in dict1:
			s += 1
		if (rr, cc - 1) not in dict1:
			s += 1
		if (rr + 1, cc) not in dict1:
			s += 1
		if (rr - 1, cc) not in dict1:
			s += 1
	print(s)


tc = int(input())
while tc > 0:
	(nr, mc, k) = list(map(int, input().split()))
	plants = {}
	fsum = 0
	for r in range(k):
		(i, j) = list(map(int, input().split()))
		plants[str(i) + '#' + str(j)] = 1
		fsum += 4
		if plants.get(str(i + 1) + '#' + str(j)) == 1:
			fsum -= 2
		if plants.get(str(i) + '#' + str(j - 1)) == 1:
			fsum -= 2
		if plants.get(str(i - 1) + '#' + str(j)) == 1:
			fsum -= 2
		if plants.get(str(i) + '#' + str(j + 1)) == 1:
			fsum -= 2
	print(fsum)
	tc = tc - 1


for i in range(int(input())):
	(n, m, k) = map(int, input().split())
	d = {}
	for i in range(k):
		(r, c) = map(int, input().split())
		d[r, c] = 1
	l = list(d.keys())
	sum1 = 0
	for i in range(len(l)):
		r1 = l[i][0]
		r2 = l[i][1]
		if (r1, r2 - 1) not in d:
			sum1 += 1
		if (r1 - 1, r2) not in d:
			sum1 += 1
		if (r1 + 1, r2) not in d:
			sum1 += 1
		if (r1, r2 + 1) not in d:
			sum1 += 1
	print(sum1)


def answer():
	val = 0
	for (i, j) in d.keys():
		if (i, j + 1) in d.keys():
			val += 1
		if (i + 1, j) in d.keys():
			val += 1
		if (i - 1, j) in d.keys():
			val += 1
		if (i, j - 1) in d.keys():
			val += 1
	return val
t = int(input())
while t:
	(n, m, k) = map(int, input().split())
	d = {}
	for i in range(k):
		(x, y) = map(int, input().split())
		d[x, y] = 1
	res = answer()
	print(k * 4 - res)
	t -= 1


t = int(input())
for _ in range(t):
	(n, m, k) = input().split()
	c = 0
	matrix = {}
	for _ in range(int(k)):
		(i, j) = map(int, input().split())
		matrix[i, j] = 1
		c += 4
		if matrix.get((i - 1, j)) == 1:
			c -= 2
		if matrix.get((i, j + 1)) == 1:
			c -= 2
		if matrix.get((i + 1, j)) == 1:
			c -= 2
		if matrix.get((i, j - 1)) == 1:
			c -= 2
	print(c)


from sys import stdin as si
for _ in range(int(si.readline().strip())):
	(_, _, k) = map(int, si.readline().strip().split())
	lookup = {}
	for i in range(k):
		(x, y) = map(int, si.readline().strip().split())

		def check(d):
			if d in lookup:
				del lookup[d]
			else:
				lookup[d] = True
		check((x - 1, y - 1, x - 1, y))
		check((x - 1, y - 1, x, y - 1))
		check((x - 1, y, x, y))
		check((x, y - 1, x, y))
	print(len(lookup))


def binarySearch(ar, l, r, x):
	if r >= l:
		mid = (l + r) // 2
		if ar[mid] == x:
			return mid
		elif ar[mid] > x:
			return binarySearch(ar, l, mid - 1, x)
		else:
			return binarySearch(ar, mid + 1, r, x)
	else:
		return -1
t = int(input())
for _ in range(t):
	(r, c, q) = map(int, input().split())
	er = []
	ar = []
	coun = 0
	for i in range(q):
		er.append(input().split())
		ar.append(int(er[i][0]) * (c + 1) + int(er[i][1]))
	ar = sorted(ar)
	for i in range(q):
		l = 0
		r = q - 1
		x = (ar[i] // (c + 1) + 1) * (c + 1) + ar[i] % (c + 1)
		if binarySearch(ar, l, r, x) == -1:
			coun += 1
		x = (ar[i] // (c + 1) - 1) * (c + 1) + ar[i] % (c + 1)
		if binarySearch(ar, l, r, x) == -1:
			coun += 1
		x = ar[i] + 1
		if i < q - 1:
			if ar[i + 1] != x:
				coun += 1
		else:
			coun += 1
		x = ar[i] - 1
		if i > 0:
			if ar[i - 1] != x:
				coun += 1
		else:
			coun += 1
	print(coun)


for _ in range(int(input())):
	(row, col, k) = list(map(int, input().split()))
	fen = 0
	garden = [[0 for i in range(col)] for j in range(row)]
	for i in range(k):
		(r, c) = list(map(int, input().split()))
		garden[r - 1][c - 1] = 1
	for c in range(col):
		for r in range(row):
			if r == 0 or r == row - 1:
				if garden[r][c] == 1:
					fen += 1
			if r != 0:
				if garden[r][c] != garden[r - 1][c]:
					fen += 1
	for r in range(row):
		for c in range(col):
			if c == 0 or c == col - 1:
				if garden[r][c] == 1:
					fen += 1
			if c != 0:
				if garden[r][c] != garden[r][c - 1]:
					fen += 1
	print(fen)


for i in range(int(input())):
	(r, c, k) = map(int, input().split())
	d = {}
	for j in range(k):
		(x, y) = map(int, input().split())
		d[x, y] = 4
		l = [(x - 1, y), (x + 1, y), (x, y + 1), (x, y - 1)]
		for i in l:
			if i in d:
				d[x, y] -= 1
				d[i] -= 1
	print(sum(d.values()))


for _ in range(int(input())):
	(n, m, k) = [int(i) for i in input().split()]
	ans = 0
	(p, q) = ([], [])
	for __ in range(k):
		(u, v) = [int(i) for i in input().split()]
		p.append((u, v))
		q.append((v, u))
		ans += 4
	p.sort()
	q.sort()
	l = [p[0]]
	reduction = 0
	for i in range(1, len(p)):
		if l[-1][0] == p[i][0] and l[-1][1] == p[i][1] - 1:
			reduction += 1
			l[-1] = p[i]
		else:
			l = [p[i]]
	l = [q[0]]
	for i in range(1, len(q)):
		if l[-1][0] == q[i][0] and l[-1][1] == q[i][1] - 1:
			reduction += 1
			l[-1] = q[i]
		else:
			l = [q[i]]
	print(ans - 2 * reduction)


def main():
	for _ in range(int(input())):
		(n, m, k) = list(map(int, input().split()))
		field = [[0] * m for _ in range(n)]
		moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		ans = 0
		while k != 0:
			(r, c) = list(map(int, input().split()))
			r -= 1
			c -= 1
			field[r][c] = 1
			for (dx, dy) in moves:
				(nr, nc) = (r + dx, c + dy)
				if nr < 0 or nr >= n or nc < 0 or (nc >= m):
					ans += 1
					continue
				if field[nr][nc] == 1:
					ans -= 1
				else:
					ans += 1
			k -= 1
		print(ans)

def __starting_point():
	main()
__starting_point()


tc = int(input())
while tc > 0:
	(nr, mc, k) = list(map(int, input().split()))
	plants = {}
	for r in range(k):
		(i, j) = list(map(int, input().split()))
		plants[str(i - 1) + '#' + str(j - 1)] = 1
	fsum = 0
	for k in plants.keys():
		(i, j) = list(map(int, k.split('#')))
		if i - 1 < 0 or i + 1 >= nr:
			fsum += 1
		if i + 1 < nr and plants.get(str(i + 1) + '#' + str(j)) is None:
			fsum += 1
		if i - 1 >= 0 and plants.get(str(i - 1) + '#' + str(j)) is None:
			fsum += 1
		if j - 1 < 0 or j + 1 >= mc:
			fsum += 1
		if j + 1 < mc and plants.get(str(i) + '#' + str(j + 1)) is None:
			fsum += 1
		if j - 1 >= 0 and plants.get(str(i) + '#' + str(j - 1)) is None:
			fsum += 1
	print(fsum)
	tc = tc - 1


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().strip().split())
	field = {}
	count = k * 4
	for i in range(k):
		(r, c) = map(int, input().strip().split())
		field[r, c] = 1
		if field.get((r - 1, c)) == 1:
			count -= 2
		if field.get((r, c - 1)) == 1:
			count -= 2
		if field.get((r + 1, c)) == 1:
			count -= 2
		if field.get((r, c + 1)) == 1:
			count -= 2
	print(count)


T = int(input())
for i in range(T):
	list2 = list(map(int, input().split()))
	N = list2[0]
	M = list2[1]
	K = list2[2]
	set1 = set()
	count = 0
	for j in range(K):
		(a, b) = map(int, input().split())
		set1.add((a, b))
	for w in set1:
		if (w[0] - 1, w[1]) not in set1:
			count = count + 1
		if (w[0] + 1, w[1]) not in set1:
			count = count + 1
		if (w[0], w[1] + 1) not in set1:
			count = count + 1
		if (w[0], w[1] - 1) not in set1:
			count = count + 1
	print(count)


def check(x, y, mat):
	tc = 0
	if mat[x - 1][y] == 0:
		tc += 1
	if mat[x][y - 1] == 0:
		tc += 1
	if mat[x][y + 1] == 0:
		tc += 1
	if mat[x + 1][y] == 0:
		tc += 1
	return tc
T = int(input())
for t in range(T):
	ls = list(map(int, input().split()))
	N = ls[0]
	M = ls[1]
	K = ls[2]
	mat = [[0 for i in range(M + 2)] for i in range(N + 2)]
	rows = []
	cols = []
	for k in range(K):
		es = list(map(int, input().split()))
		mat[es[0]][es[1]] = 1
		rows.append(es[0])
		cols.append(es[1])
	count = 0
	for i in range(len(rows)):
		count = count + check(rows[i], cols[i], mat)
	print(count)


t = int(input())
for _ in range(t):
	l = [int(x) for x in input().split()]
	n = l[0]
	m = l[1]
	k = l[2]
	d = {}
	big = []
	for _ in range(k):
		l1 = [int(x) for x in input().split()]
		l1 = (l1[0], l1[1])
		d[l1] = 1
		big.append(l1)
	c = 0
	for i in range(len(big)):
		a = (big[i][0] - 1, big[i][1])
		b = (big[i][0], big[i][1] - 1)
		c1 = (big[i][0] + 1, big[i][1])
		d1 = (big[i][0], big[i][1] + 1)
		try:
			type(d[a]) == int
		except:
			c += 1
		try:
			type(d[b]) == int
		except:
			c += 1
		try:
			type(d[c1]) == int
		except:
			c += 1
		try:
			type(d[d1]) == int
		except:
			c += 1
	print(c)


for _ in range(int(input())):
	(m, n, k) = [int(x) for x in input().strip().split()]
	g = dict()
	cnt = 0
	for i in range(k):
		(r, c) = [int(x) for x in input().strip().split()]
		g[r, c] = 0
		cnt += 4
		if (r, c - 1) in g:
			cnt -= 2
		if (r, c + 1) in g:
			cnt -= 2
		if (r - 1, c) in g:
			cnt -= 2
		if (r + 1, c) in g:
			cnt -= 2
	print(cnt)


from math import *
t = int(input())
while t > 0:
	t -= 1
	(n, m, k) = list(map(int, input().split()))
	a = []
	b = []
	ll = k * 4
	for i in range(k):
		d = [int(x) for x in input().split()]
		a.append(d)
		d = d[::-1]
		b.append(d)
	a.sort()
	b.sort()
	for i in range(1, len(a)):
		if a[i][0] == a[i - 1][0] and abs(a[i][1] - a[i - 1][1]) == 1:
			ll -= 2
	for i in range(1, len(b)):
		if b[i][0] == b[i - 1][0] and abs(b[i][1] - b[i - 1][1]) == 1:
			ll -= 2
	print(ll)


for i in range(int(input())):
	(n, m, k) = map(int, input().strip().split())
	lenth = k * 4
	matr = {}
	for j in range(k):
		(a, b) = map(int, input().strip().split())
		matr[a, b] = True
	for i in list(matr.keys()):
		(a, b) = (i[0], i[1])
		if (a - 1, b) in matr:
			lenth -= 1
		if (a + 1, b) in matr:
			lenth -= 1
		if (a, b - 1) in matr:
			lenth -= 1
		if (a, b + 1) in matr:
			lenth -= 1
	print(lenth)


for _ in range(int(input())):
	(n, m, K) = map(int, input().split())
	d = {}
	ans = 0
	for i in range(K):
		(a, b) = map(int, input().split())
		if a in d:
			d[a].append(b)
		else:
			d[a] = [b]
	for r in d:
		for j in range(len(d[r])):
			c = d[r][j]
			k = 4
			if c - 1 in d[r]:
				k -= 1
			if c + 1 in d[r]:
				k -= 1
			if r - 1 in d and c in d[r - 1]:
				k -= 1
			if r + 1 in d and c in d[r + 1]:
				k -= 1
			ans += k
	print(ans)


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	d = {}
	ct = 0
	for i in range(k):
		(r, c) = map(int, input().split())
		d[r, c] = 0
		ct += 4
		if (r, c - 1) in d:
			ct -= 2
		if (r, c + 1) in d:
			ct -= 2
		if (r - 1, c) in d:
			ct -= 2
		if (r + 1, c) in d:
			ct -= 2
	print(ct)


f = int(input())
for grid in range(f):
	field = set()
	(n, m, k) = map(int, input().split())
	for i in range(k):
		(x, y) = map(int, input().split())
		field.add((x, y))
	m = 0
	for i in field:
		if (i[0] - 1, i[1]) not in field:
			m = m + 1
		if (i[0], i[1] + 1) not in field:
			m = m + 1
		if (i[0] + 1, i[1]) not in field:
			m = m + 1
		if (i[0], i[1] - 1) not in field:
			m = m + 1
	print(m)


for i in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = []
	item = {}
	count = 0
	for j in range(k):
		(x, y) = map(int, input().split())
		ele = (x, y)
		item[ele] = 1
		a.append([x, y])
		count += 4
		if item.get((x - 1, y)) == 1:
			count -= 2
		if item.get((x, y + 1)) == 1:
			count -= 2
		if item.get((x, y - 1)) == 1:
			count -= 2
		if item.get((x + 1, y)) == 1:
			count -= 2
	print(count)


t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	s = set()
	for _ in range(k):
		(r, c) = map(int, input().split())
		s.add((r, c))
	ans = 0
	for (r, c) in s:
		ans += (r + 1, c) not in s
		ans += (r - 1, c) not in s
		ans += (r, c + 1) not in s
		ans += (r, c - 1) not in s
	print(ans)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	mat = dict()
	count = 0
	for _ in range(k):
		(r, c) = map(int, input().split())
		mat[r, c] = 'x'
		if (r, c - 1) in mat:
			count += 2
		if (r - 1, c) in mat:
			count += 2
		if (r, c + 1) in mat:
			count += 2
		if (r + 1, c) in mat:
			count += 2
	print(k * 4 - count)


for _ in range(int(input())):
	(n, m, ck) = map(int, input().split())
	a = [[]]
	pl = []
	(r1, rprev) = (-2, 0)
	fu = ck * 4
	for _ in range(ck):
		pl.append(list(map(int, input().split())))
	pl.sort()
	for i in pl:
		(r, c) = (i[0], i[1])
		if r != r1:
			a.append([])
			rprev = r1
			r1 = r
		a[-1].append(c)
		if c - 1 in a[-1]:
			fu -= 2
		if c in a[-2] and r - rprev == 1:
			fu -= 2
	print(fu)


t = int(input())
for item in range(t):
	final = set()
	(r, c, np) = map(int, input().split())
	for i in range(np):
		(pox, posy) = map(int, input().split())
		final.add((pox, posy))
	c = 0
	for i in final:
		if (i[0] - 1, i[1]) not in final:
			c = c + 1
		if (i[0], i[1] + 1) not in final:
			c = c + 1
		if (i[0] + 1, i[1]) not in final:
			c = c + 1
		if (i[0], i[1] - 1) not in final:
			c = c + 1
	print(c)


def main():
	for _ in range(int(input())):
		(n, m, k) = map(int, input().split())
		s = set()
		for _ in range(k):
			(r, c) = map(int, input().split())
			s.add((r, c))
		ans = 0
		for (r, c) in s:
			ans += (r + 1, c) not in s
			ans += (r - 1, c) not in s
			ans += (r, c + 1) not in s
			ans += (r, c - 1) not in s
		print(ans)
main()


t = int(input())
for _ in range(t):
	(n, m, k) = [int(v) for v in input().split()]
	s = {}
	c = 0
	for i in range(k):
		(x, y) = map(int, input().strip().split())
		e = (x, y)
		c += 4
		s[e] = 1
		if s.get((x - 1, y)) == 1:
			c -= 2
		if s.get((x, y - 1)) == 1:
			c -= 2
		if s.get((x + 1, y)) == 1:
			c -= 2
		if s.get((x, y + 1)) == 1:
			c -= 2
	print(c)


t = int(input())
while t != 0:
	(n, m, k) = map(int, input().split())
	d = dict()
	p = 4 * k
	l = []
	for j in range(k):
		(r, c) = map(int, input().split())
		l.append((r, c))
		if r in d:
			d[r].append(c)
		else:
			d[r] = []
			d[r].append(c)
	c = 0
	for j in l:
		if j[0] - 1 in d:
			if j[1] in d[j[0] - 1]:
				c = c + 1
		if j[0] + 1 in d:
			if j[1] in d[j[0] + 1]:
				c = c + 1
		if j[0] in d:
			if j[1] + 1 in d[j[0]]:
				c = c + 1
			if j[1] - 1 in d[j[0]]:
				c = c + 1
	print(p - c)
	t = t - 1


from collections import defaultdict
for _ in range(int(input())):
	s = set()
	(n, m, t) = [int(i) for i in input().split()]
	plant = []
	total = 0
	for i in range(t):
		(x, y) = [int(i) for i in input().split()]
		plant.append([x, y])
		s.add((x, y))
	for (x, y) in plant:
		if (x + 1, y) not in s:
			total += 1
		if (x - 1, y) not in s:
			total += 1
		if (x, y + 1) not in s:
			total += 1
		if (x, y - 1) not in s:
			total += 1
	print(total)


T = int(input())
for i in range(T):
	(N, M, K) = map(int, input().split())
	A = set()
	for i in range(K):
		A.add(tuple(map(int, input().split())))
	res = 4 * len(A)
	for (i, j) in A:
		res -= (i + 1, j) in A
		res -= (i, j + 1) in A
		res -= (i - 1, j) in A
		res -= (i, j - 1) in A
	print(res)


q = int(input())
for i in range(q):
	l = input().split()
	m = int(l[0])
	n = int(l[1])
	k = int(l[2])
	total = 0
	d = {}
	for i in range(k):
		l = input().split()
		x = int(l[0])
		y = int(l[1])
		total += 4
		d[x, y] = 1
		if d.get((x - 1, y), 0):
			total -= 2
		if d.get((x + 1, y), 0):
			total -= 2
		if d.get((x, y - 1), 0):
			total -= 2
		if d.get((x, y + 1), 0):
			total -= 2
	print(total)


from bisect import bisect_left

def BinarySearch(a, x):
	i = bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1
t = int(input())
while t != 0:
	(n, m, k) = [int(x) for x in input().split()]
	l = []
	for i in range(k):
		l.append([int(x) - 1 for x in input().split()])
	l.sort()
	count_fence = 4
	row = l[0][0]
	col = l[0][1]
	for i in range(1, k, 1):
		x = l[i][0]
		y = l[i][1]
		count_fence += 4
		if x != 0:
			res = BinarySearch(l, [x - 1, y])
			if res != -1:
				count_fence -= 2
		if y != 0 and i != 0:
			if l[i - 1][0] == x and l[i - 1][1] == y - 1:
				count_fence -= 2
	print(count_fence)
	t = t - 1


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	count = 0
	grid = {}
	for _ in range(k):
		(r, c) = map(int, input().split())
		count += 4
		if grid.get((r - 1, c)) == 1:
			count -= 2
		if grid.get((r + 1, c)) == 1:
			count -= 2
		if grid.get((r, c - 1)) == 1:
			count -= 2
		if grid.get((r, c + 1)) == 1:
			count -= 2
		grid[r, c] = 1
	print(count)


test = int(input())
for i in range(test):
	(n, m, k) = map(int, input().split())
	stat = {}
	count = 0
	for i in range(k):
		(x, y) = map(int, input().split())
		ele = (x, y)
		stat[ele] = 1
		count += 4
		if stat.get((x - 1, y)) == 1:
			count -= 2
		if stat.get((x, y + 1)) == 1:
			count -= 2
		if stat.get((x + 1, y)) == 1:
			count -= 2
		if stat.get((x, y - 1)) == 1:
			count -= 2
	print(count)


t = int(input())
for z in range(t):
	(n, m, k) = list(map(int, input().strip().split()))
	array = {}
	for i in range(k):
		(n, m) = list(map(int, input().strip().split()))
		try:
			array[n].append(m)
		except:
			array[n] = [m]
	for i in array:
		array[i].sort()
	ans = 0
	for i in array:
		for j in array[i]:
			temp = 0
			if j + 1 in array[i]:
				temp += 1
			if j - 1 in array[i]:
				temp += 1
			try:
				if j in array[i + 1]:
					temp += 1
			except:
				pass
			try:
				if j in array[i - 1]:
					temp += 1
			except:
				pass
			ans += 4 - temp
	print(ans)


T = int(input())
for _ in range(T):
	(n, m, k) = map(int, input().split())
	A = set([])
	for i in range(k):
		(a, b) = map(int, input().split())
		A.add((a, b))
	ans = 4 * len(A)
	for (a, b) in A:
		if (a - 1, b) in A:
			ans -= 1
		if (a + 1, b) in A:
			ans -= 1
		if (a, b - 1) in A:
			ans -= 1
		if (a, b + 1) in A:
			ans -= 1
	print(ans)


def check_neighbours(pdict, ptup):
	rcnt = 0
	(xcord, ycord) = (ptup[0], ptup[1])
	pkeys = pdict.keys()
	if (xcord - 1, ycord) not in pkeys:
		rcnt += 1
	if (xcord + 1, ycord) not in pkeys:
		rcnt += 1
	if (xcord, ycord - 1) not in pkeys:
		rcnt += 1
	if (xcord, ycord + 1) not in pkeys:
		rcnt += 1
	return rcnt
tnum = int(input())
for tcase in range(tnum):
	iptl = list(map(int, input().split(' ')))
	(rnum, cnum, pnum) = (iptl[0], iptl[1], iptl[2])
	pdict = {}
	for iterp in range(pnum):
		pipt = input().strip().split(' ')
		pcord = list(map(int, pipt))
		pdict[pcord[0], pcord[1]] = 1
	ftot = 0
	for ptup in pdict.keys():
		ftot += check_neighbours(pdict, ptup)
	print(ftot)


from sys import stdin
import numpy as np

def sin():
	return stdin.readline()
for _ in range(int(sin())):
	(n, m, k) = list(map(int, sin().split()))
	grid = np.zeros([n, m])
	ans = 4 * k
	for i in range(k):
		(r, c) = list(map(int, sin().split()))
		r -= 1
		c -= 1
		if r > 0 and grid[r - 1][c] == 1:
			ans -= 2
		if c > 0 and grid[r][c - 1] == 1:
			ans -= 2
		if c < m - 1 and grid[r][c + 1] == 1:
			ans -= 2
		if r < n - 1 and grid[r + 1][c] == 1:
			ans -= 2
		grid[r][c] = 1
	print(ans)


from itertools import count
from collections import Counter
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	dic = Counter()
	ans = 0
	while k:
		(x, y) = map(int, input().split())
		ans += 4
		dic[x - 1, y - 1] = 1
		k -= 1
	for pair in dic:
		(i, j) = pair
		if dic[i, j]:
			if i + 1 < n and dic[i + 1, j]:
				ans -= 1
			if j + 1 < m and dic[i, j + 1]:
				ans -= 1
			if i - 1 >= 0 and dic[i - 1, j]:
				ans -= 1
			if j - 1 >= 0 and dic[i, j - 1]:
				ans -= 1
	print(ans)


t = int(input())
while t > 0:
	t -= 1
	(n, m, k) = map(int, input().split())
	g = set([])
	for i in range(0, k):
		(a, b) = map(int, input().split())
		g.add((a, b))
	ans = 4 * len(g)
	for (a, b) in g:
		if (a, b - 1) in g:
			ans -= 1
		if (a, b + 1) in g:
			ans -= 1
		if (a - 1, b) in g:
			ans -= 1
		if (a + 1, b) in g:
			ans -= 1
	print(ans)


x = [-1, 0, 0, 1]
y = [0, -1, 1, 0]
t = int(input())
while t:
	t -= 1
	inp = input().split()
	n = int(inp[0])
	m = int(inp[1])
	k = int(inp[2])
	hmap = {}
	for i in range(k):
		inp = input().split()
		hmap[int(inp[0]) - 1, int(inp[1]) - 1] = True
	total = 0
	for key in hmap:
		if hmap[key]:
			total += 4
			for z in range(4):
				x1 = key[0] + x[z]
				y1 = key[1] + y[z]
				if x1 >= 0 and x1 < n and (y1 >= 0) and (y1 < m):
					if hmap.get((x1, y1)):
						total -= 1
	print(total)


t = int(input())
for a in range(t):
	(n, m, k) = map(int, input().split())
	mat = {}
	for b in range(k):
		(r, c) = map(int, input().split())
		mat[r - 1, c - 1] = 1
	ctr = 0
	for crd in mat.keys():
		i = list(crd)[0]
		j = list(crd)[1]
		if i == 0:
			ctr += 1
		if i == n - 1:
			ctr += 1
		if j == 0:
			ctr += 1
		if j == m - 1:
			ctr += 1
		if i - 1 >= 0 and (i - 1, j) not in mat:
			ctr += 1
		if i + 1 <= n - 1 and (i + 1, j) not in mat:
			ctr += 1
		if j - 1 >= 0 and (i, j - 1) not in mat:
			ctr += 1
		if j + 1 <= m - 1 and (i, j + 1) not in mat:
			ctr += 1
	print(ctr)


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	d = set()
	for i in range(k):
		(x, y) = map(int, input().split())
		d.add((x, y))
	cnt = 0
	for k in d:
		(i, j) = k
		for (di, dj) in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
			(x, y) = (i + di, j + dj)
			if (x, y) not in d:
				cnt += 1
	print(cnt)


def Gradient(N, M, K, paudhe):
	ans = 0
	for plant in paudhe:
		(r, l) = plant
		if (r - 1, l) not in paudhe:
			ans += 1
		if (r, l - 1) not in paudhe:
			ans += 1
		if (r + 1, l) not in paudhe:
			ans += 1
		if (r, l + 1) not in paudhe:
			ans += 1
	return ans
t = int(input())
for i in range(t):
	(N, M, K) = [int(t) for t in input().split()]
	paudhe = set()
	for j in range(K):
		paudhe.add(tuple([int(t) for t in input().split()]))
	print(Gradient(N, M, K, paudhe))