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

"It's totally fun to play troublemakers ― totally." - Lee Pace

Sakshi had a matrix with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$). Initially, all cells of this matrix contained $0$-s. Let's denote a cell in row $r$ and column $c$ by $(r, c)$.

Sakshi is well-known for troubling others. This time, her friends Nikki and Mansi planned to take revenge and teach her a lesson, so they changed her matrix by performing the following operation $Q$ times:
Choose any valid cell $(x, y)$.
Add $1$ to all the cells in row $x$.
Add $1$ to all the cells in column $y$.

For each valid $i$, the cell chosen in the $i$-th operation was $(X_{i}, Y_{i})$. Nikki and Mansi challenged Sakshi to find the number of cells in the resulting matrix which contain odd integers. Sakshi is not good at math, since she has spent all her life troubling others, so this time, she really needs your help. Help Sakshi find the answer.

------  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 $Q$.
$Q$ lines follow. For each $i$ ($1 ≤ i ≤ Q$), the $i$-th of these lines contains two space-separated integers $X_{i}$ and $Y_{i}$.

------  Output ------
For each test case, print a single line containing one integer ― the number of cells with odd values.

------  Constraints ------
$1 ≤ T ≤ 300$
$1 ≤ N, M, Q ≤ 10^{5}$
$1 ≤ X_{i} ≤ N$ for each valid $i$
$1 ≤ Y_{i} ≤ M$ for each valid $i$
the sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$
the sum of $M$ over all test cases does not exceed $3 \cdot 10^{5}$
the sum of $Q$ over all test cases does not exceed $3 \cdot 10^{5}$

------  Subtasks ------
Subtask #1 (40 points):
$1 ≤ N, M, Q ≤ 300$

Subtask #2 (40 points):
$1 ≤ T ≤ 3$
$1 ≤ N \cdot M ≤ 10^{6}$
$1 ≤ Q ≤ 10^{5}$

Subtask #3 (20 points): original constraints

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

2 2 3

1 1

1 2

2 1
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
Example case 1: After applying the first operation, the matrix becomes:

2 1
1 0

After applying the second operation, it becomes:

3 3
1 1

Finally, after applying the third operation, it becomes:

4 3
3 2

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
case = int(input())
for _ in range(case):
	(n, m, q) = map(int, input().split(' '))
	rows = {}
	col = {}
	for i in range(q):
		(x, y) = map(int, input().split(' '))
		if x not in rows:
			rows[x] = 0
		if y not in col:
			col[y] = 0
		rows[x] += 1
		col[y] += 1
	rowodds = 0
	for key in rows:
		if rows[key] & 1 == 1:
			rowodds += 1
	colodds = 0
	for key in col:
		if col[key] & 1 == 1:
			colodds += 1
	res = rowodds * m + colodds * n - rowodds * colodds * 2
	print(res)


tc = int(input())
for _ in range(tc):
	inp = list(map(int, input().split()))
	n = inp[0]
	m = inp[1]
	q = inp[2]
	rows = [0] * (n + 1)
	cols = [0] * (m + 1)
	for i in range(q):
		inp = list(map(int, input().split()))
		x = inp[0]
		y = inp[1]
		rows[x] = not rows[x]
		cols[y] = not cols[y]
	colodd = 0
	rowodd = 0
	for i in cols:
		if i:
			colodd += 1
	for i in rows:
		if i:
			rowodd += 1
	print(colodd * (n - rowodd) + rowodd * (m - colodd))


T = int(input())
for t in range(T):
	(n, m, q) = map(int, input().split())
	x = [0] * n
	y = [0] * m
	for i in range(q):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		x[a] += 1
		y[b] += 1
	x_even_num = sum([i % 2 == 0 for i in x])
	x_odd_num = n - x_even_num
	y_even_num = sum([i % 2 == 0 for i in y])
	y_odd_num = m - y_even_num
	print(x_even_num * y_odd_num + x_odd_num * y_even_num)


for _ in range(int(input())):
	(N, M, Q) = list(map(int, input().split()))
	(cols, rows) = [[0] * M, [0] * N]
	for i in range(Q):
		(X, Y) = [int(m) - 1 for m in input().split()]
		cols[Y] += 1
		rows[X] += 1
	(nco, nro) = [0, 0]
	for i in cols:
		nco += i % 2
	for j in rows:
		nro += j % 2
	print((len(rows) - nro) * nco + (len(cols) - nco) * nro)


from collections import defaultdict
for _ in range(int(input())):
	(N, M, Q) = list(map(int, input().split()))
	cols = [0] * M
	rows = [0] * N
	for i in range(Q):
		(X, Y) = list(map(int, input().split()))
		X -= 1
		Y -= 1
		cols[Y] += 1
		rows[X] += 1
	nco = 0
	nce = 0
	nro = 0
	nre = 0
	for i in cols:
		if i % 2 == 0:
			nce += 1
		else:
			nco += 1
	for j in rows:
		if j % 2 == 0:
			nre += 1
		else:
			nro += 1
	print(nro * nce + nco * nre)


from collections import Counter

def soln(n, m, q, rows, cols):
	res = 0
	r_counts = [0] * n
	for i in rows:
		r_counts[i - 1] += 1
	c_counts = [0] * m
	for i in cols:
		c_counts[i - 1] += 1
	r_odds = r_eves = 0
	for i in r_counts:
		if i & 1:
			r_odds += 1
		else:
			r_eves += 1
	c_odds = c_eves = 0
	for i in c_counts:
		if i & 1:
			c_odds += 1
		else:
			c_eves += 1
	res = r_odds * c_eves + r_eves * c_odds
	return res
for _ in range(int(input())):
	(n, m, q) = map(int, input().split())
	rows = []
	cols = []
	for i in range(q):
		(r, c) = map(int, input().split())
		rows.append(r)
		cols.append(c)
	print(soln(n, m, q, rows, cols))


for z in range(int(input())):
	(n, m, o) = [int(x) for x in input().split()]
	r = [0] * n
	c = [0] * m
	for i in range(o):
		(p, q) = [int(x) for x in input().split()]
		r[p - 1] += 1
		c[q - 1] += 1
	(re, ce) = (0, 0)
	for x in r:
		if x % 2 == 0:
			re += 1
	for x in c:
		if x % 2 == 0:
			ce += 1
	print(re * (m - ce) + ce * (n - re))


t = int(input())
for _ in range(t):
	(N, M, Q) = map(int, input().split())
	x_count = [0 for i in range(N)]
	y_count = [0 for j in range(M)]
	for _ in range(Q):
		(x, y) = input().split()
		x_count[int(x) - 1] += 1
		y_count[int(y) - 1] += 1
	x_count_odd = 0
	x_count_eve = 0
	y_count_odd = 0
	y_count_eve = 0
	for i in range(N):
		if x_count[i] % 2 == 1:
			x_count_odd += 1
		else:
			x_count_eve += 1
	for j in range(M):
		if y_count[j] % 2 == 1:
			y_count_odd += 1
		else:
			y_count_eve += 1
	print(x_count_odd * y_count_eve + x_count_eve * y_count_odd)


T = int(input())
for i in range(T):
	(N, M, Q) = map(int, input().split())
	r = [0] * N
	c = [0] * M
	for k in range(Q):
		(X, Y) = map(lambda a: int(a) - 1, input().split())
		r[X] += 1
		c[Y] += 1
	(odd, even) = (0, 0)
	for l in range(N):
		if r[l] & 1:
			odd += 1
	for m in range(M):
		if c[m] & 1 == 0:
			even += 1
	print(odd * even + (N - odd) * (M - even))


T = int(input())
for _ in range(T):
	(N, M, Q) = map(int, input().strip().split())
	row = [0] * (N + 1)
	col = [0] * (M + 1)
	for _ in range(Q):
		(X, Y) = map(int, input().strip().split())
		row[X] += 1
		col[Y] += 1
	(row_e, row_o, col_e, col_o) = (0, 0, 0, 0)
	for i in range(1, N + 1):
		if row[i] & 1 == 0:
			row_e += 1
		else:
			row_o += 1
	for i in range(1, M + 1):
		if col[i] & 1 == 0:
			col_e += 1
		else:
			col_o += 1
	val = row_e * col_o + col_e * row_o
	print(val)


for _ in range(int(input())):
	(n, m, q) = map(int, input().split())
	x = dict.fromkeys(list(range(1, n + 1)), True)
	y = dict.fromkeys(list(range(1, m + 1)), True)
	xc = yc = 0
	for i in range(q):
		(a, b) = map(int, input().split())
		x[a] = not x[a]
		y[b] = not y[b]
	for i in x:
		if x[i]:
			xc += 1
	for i in y:
		if y[i]:
			yc += 1
	print(xc * (m - yc) + yc * (n - xc))


t = int(input())
for i in range(t):
	(n, m, q) = map(int, input().split())
	a = [0] * n
	b = [0] * m
	for j in range(q):
		(r, c) = map(int, input().split())
		a[r - 1] += 1
		b[c - 1] += 1
	o1 = 0
	e1 = 0
	for k in a:
		if k % 2 == 0:
			e1 += 1
		else:
			o1 += 1
	o2 = 0
	e2 = 0
	for z in b:
		if z % 2 == 0:
			e2 += 1
		else:
			o2 += 1
	print(e2 * o1 + e1 * o2)


for _ in range(int(input())):
	(n, m, q) = map(int, input().split())
	rows = [0] * n
	cols = [0] * m
	for i in range(q):
		(row, col) = map(int, input().split())
		rows[row - 1] += 1
		cols[col - 1] += 1
	countOddr = 0
	countEvenr = 0
	for num in rows:
		if num % 2 == 0:
			countEvenr += 1
		else:
			countOddr += 1
	countOddc = 0
	countEvenc = 0
	for num in cols:
		if num % 2 == 0:
			countEvenc += 1
		else:
			countOddc += 1
	print(countEvenc * countOddr + countEvenr * countOddc)


T = int(input())
for t in range(T):
	(n, m, Q) = map(int, input().split())
	arrx = [0 for i in range(n)]
	arry = [0 for i in range(m)]
	for q in range(Q):
		(a, b) = map(int, input().split())
		arrx[a - 1] += 1
		arry[b - 1] += 1
	dic = {'cnt_ev': 0, 'cnt_odd': 0}
	for i in arrx:
		if i % 2 == 0:
			dic['cnt_ev'] += 1
		else:
			dic['cnt_odd'] += 1
	ans = 0
	for i in arry:
		if i % 2 == 0:
			ans += dic['cnt_odd']
		else:
			ans += dic['cnt_ev']
	print(ans)


for _ in range(int(input())):
	(n, m, q) = map(int, input().split())
	rows = [0 for i in range(n)]
	cols = [0 for i in range(m)]
	for k in range(q):
		(x, y) = map(int, input().split())
		if rows[x - 1] == 1:
			rows[x - 1] = 0
		else:
			rows[x - 1] = 1
		if cols[y - 1] == 1:
			cols[y - 1] = 0
		else:
			cols[y - 1] = 1
	one_rows = 0
	one_cols = 0
	for i in rows:
		if i == 1:
			one_rows += 1
	for j in cols:
		if j == 1:
			one_cols += 1
	res = one_rows * m + one_cols * n - 2 * (one_rows * one_cols)
	print(res)


for _ in range(int(input())):
	(n, m, q) = map(int, input().split())
	rn = [0] * n
	rm = [0] * m
	for __ in range(q):
		(i, j) = map(int, input().split())
		rn[i - 1] ^= 1
		rm[j - 1] ^= 1
	r = rn.count(1)
	c = rm.count(1)
	print(r * m + c * n - 2 * r * c)


def solve():
	odds = len(x_cha) * m - 2 * len(x_cha) * len(y_cha) + n * len(y_cha)
	print(odds)
t = int(input())
for _ in range(t):
	(n, m, q) = list(map(int, input().split()))
	x_cha = set()
	y_cha = set()
	for i in range(q):
		(x, y) = list(map(int, input().split()))
		if x in x_cha:
			x_cha.remove(x)
		else:
			x_cha.add(x)
		if y in y_cha:
			y_cha.remove(y)
		else:
			y_cha.add(y)
	solve()


t = int(input())
for _ in range(t):
	(n, m, q) = map(int, input().split())
	rows_cnt = [0] * (n + 1)
	cols_cnt = [0] * (m + 1)
	for _ in range(q):
		(x, y) = map(int, input().split())
		rows_cnt[x] += 1
		cols_cnt[y] += 1
	odd_rows = 0
	odd_cols = 0
	even_rows = 0
	even_cols = 0
	for i in range(1, n + 1):
		if rows_cnt[i] % 2 == 0:
			even_rows += 1
		else:
			odd_rows += 1
	for i in range(1, m + 1):
		if cols_cnt[i] % 2 == 0:
			even_cols += 1
		else:
			odd_cols += 1
	val = odd_cols * even_rows + even_cols * odd_rows
	print(val)


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time
import bisect

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

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

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def main():
	for _ in tr():
		(n, m, q) = sm()
		rows = [0] * n
		cols = [0] * m
		for __ in range(q):
			(x, y) = sm()
			rows[x - 1] += 1
			cols[y - 1] += 1
		row_odd = 0
		col_odd = 0
		for i in rows:
			if i & 1:
				row_odd += 1
		for i in cols:
			if i & 1:
				col_odd += 1
		print((m - col_odd) * row_odd + (n - row_odd) * col_odd)
main()


T = int(input())
from collections import Counter

def is_even(n):
	if n % 2 == 0:
		return True
	else:
		return False
for _ in range(T):
	(N, M, Q) = list(map(int, input().split()))
	(ls_xi, ls_yi) = ([], [])
	(ctr_xi, ctr_yi) = (Counter(), Counter())
	for _ in range(Q):
		(xi, yi) = list(map(int, input().split()))
		ctr_xi.update([xi])
		ctr_yi.update([yi])
	evenx = len(list(filter(is_even, ctr_xi.values())))
	if len(ctr_xi) < N:
		evenx = evenx + N - len(ctr_xi)
	oddx = N - evenx
	eveny = len(list(filter(is_even, ctr_yi.values())))
	if len(ctr_yi) < M:
		eveny = eveny + M - len(ctr_yi)
	oddy = M - eveny
	print(evenx * oddy + oddx * eveny)


def operationsOnMatrix():
	t = int(input())
	for _ in range(t):
		(n, m, q) = map(int, input().split())
		rows = [0 for i in range(n)]
		cols = [0 for i in range(m)]
		for i in range(q):
			(row, col) = map(int, input().split())
			rows[row - 1] += 1
			cols[col - 1] += 1
		countEvenR = 0
		countOddR = 0
		for num in rows:
			if num % 2:
				countOddR += 1
			else:
				countEvenR += 1
		countOddC = 0
		countEvenC = 0
		for num in cols:
			if num % 2:
				countOddC += 1
			else:
				countEvenC += 1
		print(countOddR * countEvenC + countOddC * countEvenR)
operationsOnMatrix()


T = int(input())
for i in range(T):
	(n, m, q) = map(int, input().split())
	row = [0] * n
	column = [0] * m
	for i in range(q):
		(a, b) = map(int, input().split())
		row[a - 1] += 1
		column[b - 1] += 1
	(even1, even2, odd1, odd2) = (0, 0, 0, 0)
	for i in range(n):
		if row[i] % 2 == 0:
			even1 += 1
		if row[i] % 2 != 0:
			odd1 += 1
	for i in range(m):
		if column[i] % 2 == 0:
			even2 += 1
		if column[i] % 2 != 0:
			odd2 += 1
	print(even1 * odd2 + even2 * odd1)


for t in range(int(input())):
	(n, m, Q) = map(int, input().split())
	arrx = [0 for x in range(n)]
	arry = [0 for x in range(m)]
	for q in range(Q):
		(a, b) = map(int, input().split())
		arrx[a - 1] += 1
		arry[b - 1] += 1
		dic = {'even': 0, 'odd': 0}
	for i in arrx:
		if i % 2 == 0:
			dic['even'] += 1
		else:
			dic['odd'] += 1
	count = 0
	for i in arry:
		if i % 2 == 0:
			count += dic['odd']
		else:
			count += dic['even']
	print(count)


T = int(input())
for i in range(T):
	(N, M, Q) = map(int, input().split())
	rows = [0] * (N + 1)
	columns = [0] * (M + 1)
	for i in range(Q):
		(r, c) = map(int, input().split())
		rows[r] += 1
		columns[c] += 1
	i = 1
	count = 0
	odd = 0
	even = 0
	zero = 0
	while i <= N:
		if rows[i] != 0:
			if rows[i] % 2 == 0:
				even += 1
			else:
				odd += 1
		else:
			zero += 1
		i += 1
	i = 1
	while i <= M:
		if columns[i] != 0:
			if columns[i] % 2 != 0:
				count += even + zero
			else:
				count += odd
		else:
			count += odd
		i += 1
	print(count)


t = int(input())
for k in range(t):
	(a, b, c) = map(int, input().split())
	(rl, cl) = ([0] * a, [0] * b)
	for i in range(c):
		(r, c) = map(int, input().split())
		rl[r - 1] += 1
		cl[c - 1] += 1
	xe = xo = ye = yo = 0
	for i in rl:
		if i % 2 == 0:
			xe += 1
		else:
			xo += 1
	for i in cl:
		if i % 2 == 0:
			ye += 1
		else:
			yo += 1
	p = ye * xo
	q = yo * xe
	print(p + q)


for _ in range(int(input())):
	(n, m, q) = map(int, input().split())
	a = [0] * n
	b = [0] * m
	odds = 0
	while q:
		q -= 1
		(x, y) = map(int, input().split())
		a[x - 1] += 1
		b[y - 1] += 1
		a[x - 1] %= 2
		b[y - 1] %= 2
	rows = 0
	cols = 0
	for i in range(n):
		if a[i] > 0:
			rows += 1
	for i in range(m):
		if b[i] > 0:
			cols += 1
	odds += (m - cols) * rows
	odds += (n - rows) * cols
	print(odds)


for _ in range(int(input())):
	(n, m, q) = list(map(int, input().split()))
	row = [0] * n
	col = [0] * m
	(re, ro, ce, co) = (0, 0, 0, 0)
	for _ in range(q):
		(x, y) = map(int, input().split())
		row[x - 1] += 1
		col[y - 1] += 1
	for i in row:
		if i % 2 == 0:
			re += 1
		else:
			ro += 1
	for i in col:
		if i % 2 == 0:
			ce += 1
		else:
			co += 1
	print(ro * ce + re * co)


t = int(input())
while t:
	(n, m, q) = map(int, input().split())
	ans = 0
	r = []
	c = []
	o1 = o2 = e1 = e2 = 0
	for i in range(n):
		r.append(0)
	for i in range(m):
		c.append(0)
	for i in range(q):
		(x, y) = map(int, input().split())
		r[x - 1] += 1
		c[y - 1] += 1
	for i in range(len(r)):
		if r[i] % 2 == 0:
			e1 += 1
		else:
			o1 += 1
	for i in range(len(c)):
		if c[i] % 2 == 0:
			e2 += 1
		else:
			o2 += 1
	print(o2 * e1 + o1 * e2)
	t = t - 1


for _ in range(int(input())):
	(n, m, q) = map(int, input().split())
	(rows, cols) = ({}, {})
	for i in range(1, n + 1):
		rows[i] = 0
	for i in range(1, m + 1):
		cols[i] = 0
	for _ in range(q):
		(r, c) = map(int, input().split())
		(rows[r], cols[c]) = (rows[r] + 1, cols[c] + 1)
	(odd1, even1, odd2, even2, ans) = (0, 0, 0, 0, 0)
	for i in cols.values():
		if i % 2 == 1:
			odd2 += 1
		else:
			even2 += 1
	for i in rows.values():
		if i % 2 == 1:
			ans += even2
		else:
			ans += odd2
	print(ans)


test = int(input())

def solve():
	entries = list(map(int, input().split()))
	(a, b, c, d) = (0, 0, 0, 0)
	row = []
	col = []
	for i in range(entries[0]):
		row.append(0)
	for j in range(entries[1]):
		col.append(0)
	for p in range(entries[2]):
		cells = input().split()
		row[int(cells[0]) - 1] += 1
		col[int(cells[1]) - 1] += 1
		row[int(cells[0]) - 1] %= 2
		col[int(cells[1]) - 1] %= 2
	for k in range(entries[0]):
		if row[k] == 1:
			a += 1
		else:
			b += 1
	for l in range(entries[1]):
		if col[l] == 1:
			c += 1
		else:
			d += 1
	result = a * d + c * b
	print(result)
for q in range(test):
	solve()


import numpy as np
t = int(input())
while t > 0:
	(n, m, q) = map(int, input().split())
	A = [0 for x in range(n)]
	B = [0 for x in range(m)]
	while q != 0:
		(x, y) = map(int, input().split())
		x = x - 1
		y -= 1
		A[x] += 1
		B[y] += 1
		q -= 1
	od1 = 0
	eve1 = 0
	od2 = 0
	eve2 = 0
	for i in range(0, len(A)):
		if A[i] % 2 == 0:
			eve1 += 1
		else:
			od1 += 1
	for j in range(0, len(B)):
		if B[j] % 2 == 0:
			eve2 += 1
		else:
			od2 += 1
	print(eve1 * od2 + eve2 * od1)
	t -= 1


for _ in range(int(input())):
	(n, m, q) = map(int, input().split())
	rows = {}
	cols = {}
	for i in range(1, n + 1):
		rows[i] = 0
	for i in range(1, m + 1):
		cols[i] = 0
	for _ in range(q):
		(r, c) = map(int, input().split())
		rows[r] += 1
		cols[c] += 1
	ans = 0
	(o1, e1, o2, e2) = (0, 0, 0, 0)
	for i in cols.values():
		if i % 2 == 1:
			o2 += 1
		else:
			e2 += 1
	for i in rows.values():
		if i % 2 == 1:
			ans += e2
		else:
			ans += o2
	print(ans)


T = int(input())
for i in range(T):
	(N, M, Q) = map(int, input().split())
	oddN = 0
	oddM = 0
	r = [0] * N
	c = [0] * M
	for i in range(Q):
		(X, Y) = map(int, input().split())
		r[X - 1] += 1
		c[Y - 1] += 1
	for i in r:
		if i % 2 == 1:
			oddN += 1
	for i in c:
		if i % 2 == 1:
			oddM += 1
	count = oddN * (M - oddM) + oddM * (N - oddN)
	print(count)


t = int(input())
for _ in range(t):
	(n, m, q) = list(map(int, input().split()))
	arrn = [0] * n
	arrm = [0] * m
	for _ in range(q):
		(x, y) = list(map(int, input().split()))
		arrn[x - 1] = arrn[x - 1] ^ 1
		arrm[y - 1] = arrm[y - 1] ^ 1
	countn = arrn.count(1)
	countm = arrm.count(1)
	print((m - countm) * countn + (n - countn) * countm)


t = int(input())
for i in range(t):
	(n, m, q) = map(int, input().split())
	l = [0] * n
	l1 = [0] * m
	for i in range(q):
		(x, y) = map(int, input().split())
		l[x - 1] += 1
		l1[y - 1] += 1
	c = 0
	c1 = 0
	for i in range(n):
		if l[i] % 2 == 0:
			c = c + 1
		else:
			c1 = c1 + 1
	c2 = 0
	c3 = 0
	for i in range(m):
		if l1[i] % 2 == 0:
			c2 = c2 + 1
		else:
			c3 = c3 + 1
	print(c * c3 + c1 * c2)


for i in range(int(input())):
	(n, m, q) = map(int, input().split())
	row = [0 for i in range(n)]
	col = [0 for i in range(m)]
	(r, c) = (0, 0)
	for i in range(q):
		(a, b) = map(int, input().split())
		row[a - 1] += 1
		col[b - 1] += 1
	for i in row:
		if i % 2 != 0:
			r += 1
	for i in col:
		if i % 2 != 0:
			c += 1
	print(r * m + c * n - 2 * r * c)


for iterator in range(int(input())):
	(n, m, q) = map(int, input().split())
	col = [0] * n
	row = [0] * m
	for i in range(q):
		(x, y) = map(int, input().split())
		col[x - 1] += 1
		row[y - 1] += 1
	o1 = 0
	o2 = 0
	e1 = 0
	e2 = 0
	for x in col:
		if x % 2 == 0:
			e1 += 1
		else:
			o1 += 1
	for x in row:
		if x % 2 == 0:
			e2 += 1
		else:
			o2 += 1
	ans = e1 * o2 + e2 * o1
	print(ans)


try:
	t = int(input())
	while t > 0:
		(n, m, q) = map(int, input().split())
		n1 = [0] * m
		m1 = [0] * n
		while q > 0:
			(x, y) = input().split()
			(x, y) = (int(x) - 1, int(y) - 1)
			n1[y] = (n1[y] + 1) % 2
			m1[x] = (m1[x] + 1) % 2
			q -= 1
		n2 = n1.count(1)
		m2 = m1.count(1)
		print(n * n2 + m * m2 - 2 * (m2 * n2))
		t += 1
except:
	pass


t = int(input())
while t != 0:
	t -= 1
	(n, m, q) = [int(x) for x in input().split()]
	r = [0 for x in range(n)]
	c = [0 for x in range(m)]
	while q != 0:
		q -= 1
		(a, b) = [int(x) for x in input().split()]
		r[a - 1] += 1
		c[b - 1] += 1
	count1 = 0
	for i in range(n):
		if r[i] % 2 != 0:
			count1 += 1
	count2 = 0
	for i in range(m):
		if c[i] % 2 != 0:
			count2 += 1
	print(count1 * (m - count2) + (n - count1) * count2)


p = int(input())
for i in range(p):
	(n, m, q) = map(int, input().split())
	h = [0] * n
	k = [0] * m
	a = 0
	b = 0
	for j in range(q):
		(x, y) = map(int, input().split())
		h[x - 1] = h[x - 1] + 1
		k[y - 1] = k[y - 1] + 1
	for j in h:
		if j % 2 != 0:
			a = a + 1
	for j in k:
		if j % 2 != 0:
			b = b + 1
	u = a * (len(k) - b) + b * (len(h) - a)
	print(u)


t = int(input())
while t > 0:
	(r, c, q) = map(int, input().split())
	rowl = [0 for i in range(c)]
	coll = [0 for i in range(r)]
	while q > 0:
		(x, y) = map(int, input().split())
		coll[x - 1] += 1
		rowl[y - 1] += 1
		q -= 1
	codd = 0
	rodd = 0
	for i in range(c):
		if rowl[i] % 2 != 0:
			rodd += 1
	for i in range(r):
		if coll[i] % 2 != 0:
			codd += 1
	reven = c - rodd
	ceven = r - codd
	c = rodd * ceven + reven * codd
	t = t - 1
	print(c)


for i in range(int(input())):
	(n, m, q) = list(map(int, input().split(' ')))
	r = [0] * n
	c = [0] * m
	for j in range(q):
		(x, y) = list(map(int, input().split(' ')))
		r[x - 1] += 1
		c[y - 1] += 1
	(rec, ro, ce, co) = (0, 0, 0, 0)
	for k in range(n):
		if r[k] % 2 == 0:
			rec += 1
		else:
			ro += 1
	for k in range(m):
		if c[k] % 2 == 0:
			ce += 1
		else:
			co += 1
	print(ro * ce + rec * co)


for _ in range(int(input())):
	(n, m, q) = list(map(int, input().split()))
	row = [0] * n
	col = [0] * m
	for i in range(q):
		(x, y) = list(map(int, input().split()))
		row[x - 1] += 1
		col[y - 1] += 1
	(row_even, row_odd) = (0, 0)
	(col_even, col_odd) = (0, 0)
	for i in row:
		if i % 2 == 0:
			row_even += 1
		else:
			row_odd += 1
	for i in col:
		if i % 2 == 0:
			col_even += 1
		else:
			col_odd += 1
	print(col_even * row_odd + row_even * col_odd)


for _ in range(int(input())):
	(n, m, q) = map(int, input().split())
	e = 0
	o = 0
	ans = 0
	r = [0 for i in range(n)]
	c = [0 for i in range(m)]
	for i in range(q):
		(x, y) = map(int, input().split())
		r[x - 1] += 1
		c[y - 1] += 1
	for i in range(n):
		if r[i] % 2 == 0:
			e += 1
		else:
			o += 1
	for i in range(m):
		if c[i] % 2 == 0:
			ans += o
		else:
			ans += e
	print(ans)


T = int(input())
for _ in range(T):
	[N, M, Q] = list(map(int, input().split()))
	rows = set()
	cols = set()
	for _ in range(Q):
		[x, y] = list(map(int, input().split()))
		if x in rows:
			rows.remove(x)
		else:
			rows.add(x)
		if y in cols:
			cols.remove(y)
		else:
			cols.add(y)
	r = len(rows)
	c = len(cols)
	print(r * M + c * N - 2 * r * c)


t = int(input())
for _ in range(t):
	(n, m, q) = list(map(int, input().strip().split(' ')))
	r = []
	c = []
	for i in range(q):
		l = list(map(int, input().strip().split(' ')))[:2]
		(r.append(l[0] - 1), c.append(l[1] - 1))
	r = sorted(r)
	c = sorted(c)
	row = []
	column = []
	for i in range(n):
		row.append(0)
	for i in range(m):
		column.append(0)
	for i in r:
		row[i] += 1
	for i in c:
		column[i] += 1
	count1 = 0
	count2 = 0
	count3 = 0
	count4 = 0
	for i in row:
		if i % 2 == 1:
			count1 += 1
		else:
			count3 += 1
	for i in column:
		if i % 2 == 1:
			count2 += 1
		else:
			count4 += 1
	print(count1 * count4 + count2 * count3)


from collections import Counter

def find(n, m, N, M):
	z = sum(n.values())
	c = 0
	for i in range(M):
		if m[i]:
			c += N - z
		else:
			c += z
	return c

def main():
	for _ in range(int(input())):
		(N, M, Q) = list(map(int, input().split()))
		an = Counter()
		am = Counter()
		for __ in range(Q):
			(a, b) = list(map(int, input().split()))
			an[a - 1] = 1 - an[a - 1]
			am[b - 1] = 1 - am[b - 1]
		print(find(an, am, N, M))
main()


t = int(input())
for _ in range(t):
	(m, n, q) = [int(x) for x in input().split()]
	query = []
	for i in range(q):
		query.append([int(x) for x in input().split()])
	row = [0 for x in range(m)]
	column = [0 for x in range(n)]
	for i in query:
		row[i[0] - 1] += 1
		column[i[1] - 1] += 1
	odd = 0
	even_row = 0
	odd_row = 0
	even_column = 0
	odd_column = 0
	for i in row:
		if i % 2:
			odd_row += 1
		else:
			even_row += 1
	for i in column:
		if i % 2:
			odd_column += 1
		else:
			even_column += 1
	answer = odd_row * even_column + even_row * odd_column
	print(answer)


try:
	for t in range(int(input())):
		(n, m, q) = map(int, input().split())
		row = [0] * n
		col = [0] * m
		for i in range(q):
			(x, y) = map(int, input().split())
			(x, y) = (x - 1, y - 1)
			row[x] = (row[x] + 1) % 2
			col[y] = (col[y] + 1) % 2
		(even1, even2, odd1, odd2) = (0, 0, 0, 0)
		for i in row:
			if i == 0:
				even1 += 1
			else:
				odd1 += 1
		for j in col:
			if j == 0:
				even2 += 1
			else:
				odd2 += 1
		ans = even1 * odd2 + even2 * odd1
		print(ans)
except:
	pass


t = int(input())
while t > 0:
	odc = odr = ec = er = 0
	(n, m, q) = map(int, input().split(' '))
	r = [0] * n
	c = [0] * m
	for i in range(q):
		(row, col) = map(int, input().split(' '))
		r[row - 1] = r[row - 1] + 1
		c[col - 1] = c[col - 1] + 1
	for i in r:
		if i % 2 == 0:
			er = er + 1
		else:
			odr = odr + 1
	for j in c:
		if j % 2 == 0:
			ec = ec + 1
		else:
			odc = odc + 1
	print(er * odc + ec * odr)
	t = t - 1


for _ in range(int(input())):
	(n, m, q) = map(int, input().split())
	(row, col) = ({}, {})
	for i in range(1, n + 1):
		row[i] = 0
	for i in range(1, m + 1):
		col[i] = 0
	for k in range(q):
		(x, y) = map(int, input().split())
		row[x] += 1
		col[y] += 1
	(countr, countc) = (0, 0)
	ans = 0
	for i in row:
		if row[i] % 2 == 0:
			countr += 1
	for i in col:
		if col[i] % 2 == 0:
			countc += 1
	ans += countr * m
	ans -= 2 * (countr * countc)
	ans += countc * n
	print(ans)


for _ in range(int(input())):
	(n, m, q) = map(int, input().split())
	dr = {}
	dc = {}
	cs = set()
	for i in range(q):
		(e1, e2) = input().split()
		e1 = int(e1)
		e2 = int(e2)
		cs.add(e1)
		if e1 in dr:
			if e2 in dc:
				dr[e1] = dr[e1] + 1
				dc[e2] = dc[e2] + 1
			else:
				dr[e1] = dr[e1] + 1
				dc[e2] = 1
		elif e2 in dc:
			dr[e1] = 1
			dc[e2] = dc[e2] + 1
		else:
			dr[e1] = 1
			dc[e2] = 1
	cs = list(cs)
	odd = 0
	for u in cs:
		no = dr[u]
		if no % 2 != 0:
			odd = odd + 1
	even = n - odd
	res = 0
	i = 1
	while i <= m:
		if i in dc:
			nok = dc[i]
		else:
			nok = 0
		if nok % 2 != 0:
			res = res + even
		else:
			res = res + odd
		i = i + 1
	print(res)


t = int(input())
for _ in range(t):
	inp = input().split()
	n = int(inp[0])
	m = int(inp[1])
	q = int(inp[2])
	rr = [0 for i in range(n)]
	cc = [0 for i in range(m)]
	for i in range(q):
		inp = input().split()
		r = int(inp[0]) - 1
		c = int(inp[1]) - 1
		rr[r] = (rr[r] + 1) % 2
		cc[c] = (cc[c] + 1) % 2
	er = rr.count(0)
	od = len(rr) - er
	ec = cc.count(0)
	oc = len(cc) - ec
	c = od * ec + er * oc
	print(c)


for _ in range(int(input())):
	(n, m, q) = map(int, input().split())
	rows = {}
	cols = {}
	for i in range(1, n + 1):
		rows[i] = 0
	for i in range(1, m + 1):
		cols[i] = 0
	for _ in range(q):
		(r, c) = map(int, input().split())
		rows[r] += 1
		cols[c] += 1
	ocount = ecount = 0
	for i in range(1, n + 1):
		(ocount, ecount) = (ocount + 1, ecount) if rows[i] % 2 != 0 else (ocount, ecount + 1)
	res = 0
	for j in range(1, m + 1):
		res += ecount if cols[j] % 2 != 0 else ocount
	print(res)


T = int(input())
for i in range(T):
	(N, M, Q) = map(int, input().split())
	lr = []
	lc = []
	for j in range(N):
		lr.append(0)
	for j in range(M):
		lc.append(0)
	for j in range(Q):
		(x, y) = map(int, input().split())
		lr[x - 1] = (lr[x - 1] + 1) % 2
		lc[y - 1] = (lc[y - 1] + 1) % 2
	a = 0
	b = 0
	for j in range(N):
		if lr[j] == 1:
			a += 1
	for j in range(M):
		if lc[j] == 1:
			b += 1
	print(a * M + b * N - 2 * a * b)


try:
	t = int(input())
	for _ in range(t):
		(n, m, q) = map(int, input().split())
		rows = [0] * n
		columns = [0] * m
		for i in range(q):
			(x, y) = map(int, input().split())
			rows[x - 1] += 1
			columns[y - 1] += 1
		r = 0
		c = 0
		for i in rows:
			if i % 2 == 1:
				r += 1
		for i in columns:
			if i % 2 == 1:
				c += 1
		print(r * m + c * n - 2 * r * c)
except:
	pass


for _ in range(int(input())):
	(n, m, q) = map(int, input().split())
	rows = {}
	cols = {}
	for i in range(1, n + 1):
		rows[i] = 0
	for i in range(1, m + 1):
		cols[i] = 0
	for _ in range(q):
		(r, c) = map(int, input().split())
		rows[r] += 1
		cols[c] += 1
	os = es = 0
	for i in range(1, n + 1):
		(os, es) = (os + 1, es) if rows[i] % 2 == 1 else (os, es + 1)
	rs = 0
	for i in range(1, m + 1):
		rs += es if cols[i] % 2 == 1 else os
	print(rs)


from sys import stdin, stdout
import numpy as np
T = int(stdin.readline())
for _ in range(T):
	(N, M, Q) = stdin.readline().split()
	N = int(N)
	M = int(M)
	Q = int(Q)
	XX = np.zeros(N)
	YY = np.zeros(M)
	for i in range(Q):
		(X, Y) = stdin.readline().split()
		X = int(X) - 1
		Y = int(Y) - 1
		XX[X] += 1
		YY[Y] += 1
	y_odd = 0
	count = 0
	x_odd = 0
	if len(YY) <= len(XX):
		for d in range(len(YY)):
			if YY[d] % 2 != 0:
				y_odd += 1
		for j in range(len(XX)):
			if XX[j] % 2 == 0:
				count += y_odd
			else:
				count += M - y_odd
	else:
		for s in range(len(XX)):
			if XX[s] % 2 != 0:
				x_odd += 1
		for w in range(len(YY)):
			if YY[w] % 2 == 0:
				count += x_odd
			else:
				count += N - x_odd
	print(int(count))


t = int(input())
for _ in range(t):
	(n, m, q) = map(int, input().split())
	rows = {i: 0 for i in range(1, n + 1)}
	cols = {i: 0 for i in range(1, m + 1)}
	for _ in range(q):
		(x, y) = map(int, input().split())
		rows[x] += 1
		cols[y] += 1
	evenr = sum((1 for i in rows.values() if not i & 1))
	oddr = sum((1 for i in rows.values() if i & 1))
	evenc = sum((1 for i in cols.values() if not i & 1))
	oddc = sum((1 for i in cols.values() if i & 1))
	print(evenr * oddc + oddr * evenc)


import numpy as np
for _ in range(int(input())):
	(n, m, q) = map(int, input().split())
	mat = np.zeros(n)
	mat2 = np.zeros(m)
	l = []
	for i in range(q):
		(x, y) = map(int, input().split())
		mat[x - 1] = mat[x - 1] + 1
		mat2[y - 1] = mat2[y - 1] + 1
	e = 0
	o = 0
	for i in range(n):
		if mat[i] % 2 == 0:
			e = e + 1
		else:
			o = o + 1
	c = 0
	for i in range(m):
		if mat2[i] % 2 == 0:
			c = c + o
		else:
			c = c + e
	print(c)


t = int(input(''))
for xxx in range(t):
	s = input('').split(' ')
	r = int(s[0])
	c = int(s[1])
	q = int(s[2])
	a = [0] * r
	b = [0] * c
	for i in range(q):
		s = input('').split(' ')
		x = int(s[0])
		y = int(s[1])
		a[x - 1] += 1
		b[y - 1] += 1
	even1 = 0
	odd1 = 0
	for i in range(len(a)):
		if a[i] % 2 == 0:
			even1 += 1
		else:
			odd1 += 1
	even2 = 0
	odd2 = 0
	for i in range(len(b)):
		if b[i] % 2 == 0:
			even2 += 1
		else:
			odd2 += 1
	print(even1 * odd2 + even2 * odd1)


t = int(input())
while t:
	t -= 1
	(m, n, q) = map(int, input().split())
	row = [0 for i in range(m)]
	col = [0 for i in range(n)]
	for i in range(q):
		(x, y) = map(int, input().split())
		row[x - 1] = (row[x - 1] + 1) % 2
		col[y - 1] = (col[y - 1] + 1) % 2
	x = row.count(1)
	y = col.count(1)
	abc = n * x + (m - x) * y - x * y
	print(abc)