How many ways are there to place a black and a white knight on an N * M chessboard such that they do not attack each other? The knights have to be placed on different squares. A knight can move two squares horizontally and one square vertically, or two squares vertically and one square horizontally. The knights attack each other if one can reach the other in one move.

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

The first line contains the number of test cases T. Each of the next T lines contains two integers N and M.

------ Output : ------ 

Output T lines, one for each test case, each containing the required answer for the corresponding test case.

------ Constraints : ------ 

1 ≤ T ≤ 10000
1 ≤ N,M ≤ 100000

----- Sample Input 1 ------ 
3
2 2
2 3
4 5
----- Sample Output 1 ------ 
12
26
312

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(n, m) = input().split(' ')
	n = int(n)
	m = int(m)
	ans = int(0)
	if n > 2 and m > 1:
		ans = ans + (n - 2) * (m - 1) * 2
	if m > 2 and n > 1:
		ans = ans + (m - 2) * (n - 1) * 2
	ans = n * m * (n * m - 1) - 2 * ans
	print(ans)


test_cases = int(input())
for i in range(test_cases):
	(n, m) = input().split()
	m = int(m)
	n = int(n)
	if m > n:
		(n, m) = (m, n)
	if m == 1 or n == 1:
		print(n * (n - 1))
	else:
		out = n * m * (n * m - 1) - 4 * ((n - 1) * (m - 2) + (n - 2) * (m - 1))
		print(out)


t = int(input())
while t:
	(m, n) = [int(x) for x in input().split()]
	prod = m * n
	ans = prod * (prod - 1)
	if m > n:
		(m, n) = (n, m)
	if m == 1:
		ans = n * (n - 1)
	else:
		ans = ans - 4 * ((n - 2) * (m - 1) + (m - 2) * (n - 1))
	print(ans)
	t -= 1


def main():
	for _ in range(int(input())):
		(n, m) = list(map(int, input().split()))
		if n == 1:
			print(m * (m - 1))
		elif m == 1:
			print(n * (n - 1))
		else:
			print(n * m * (n * m - 1) - 4 * ((m - 2) * (n - 1) + (m - 1) * (n - 2)))
main()


t = int(input())
while t != 0:
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	if n < m:
		(n, m) = (m, n)
	if n == 1 or m == 1:
		print(n * (n - 1))
	else:
		out = n * m * (n * m - 1) - 4 * ((n - 2) * (m - 1) + (n - 1) * (m - 2))
		print(out)
	t = t - 1


t = int(input())
for i in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	if n < m:
		(n, m) = (m, n)
	if n == 1 or m == 1:
		print(n * (n - 1))
	else:
		foo = n * m * (n * m - 1) - 4 * ((n - 2) * (m - 1) + (n - 1) * (m - 2))
		print(foo)


for _ in range(int(input())):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	if n < m:
		(n, m) = (m, n)
	if m == 1 or n == 1:
		print(n * (n - 1))
	else:
		out = n * m * (n * m - 1) - 4 * ((n - 2) * (m - 1) + (n - 1) * (m - 2))
		print(out)


def main():
	t = int(input())
	for i in range(0, t):
		nm = str(input())
		n = int(nm.split(' ')[0])
		m = int(nm.split(' ')[1])
		if n == 1 or m == 1:
			if n == 1 and m == 1:
				total = 0
			else:
				greater = n if n != 1 else m
				total = greater * (greater - 1)
		else:
			total = n * m * (n * m - 1) - 8 * n * m + 12 * n + 12 * m - 16
		print(total)
main()


for i in range(int(input())):
	(m, n) = list(map(int, input().split()))
	if m > n:
		(m, n) = (n, m)
	if m == 1:
		print(n * (n - 1))
	else:
		print((m * n) ** 2 - 9 * m * n + 12 * m + 12 * n - 16)


def main():
	t = int(input())
	i = 0
	while i < t:
		i += 1
		arr = input().split()
		a = int(arr[0])
		b = int(arr[1])
		if a == 1:
			print(b * (b - 1))
		elif b == 1:
			print(a * (a - 1))
		else:
			print(a * a * b * b - (3 * a - 4) * (3 * b - 4))
main()


t = int(input())
while t != 0:
	(m, n) = input().split()
	m = int(m)
	n = int(n)
	if m == 1:
		x = n * (n - 1)
	elif n == 1:
		x = m * (m - 1)
	else:
		x = m * n * (m * n - 1) - 8 * (n - 1) * (m - 1) + 4 * (m + n - 2)
	print(x)
	t -= 1


testcases = int(input())
for i in range(testcases):
	(cols, rows) = input().split()
	cols = int(cols)
	rows = int(rows)
	if cols < rows:
		(cols, rows) = (rows, cols)
	if cols == 1 or rows == 1:
		output = cols * (cols - 1)
	else:
		output = cols * rows * (cols * rows - 1) - 2 * (2 * (rows - 1) * (cols - 2) + 2 * (rows - 2) * (cols - 1))
	print(output)