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

Chef Ada is training to defend her title of World Chess Champion.

To train her calculation skills, Ada placed a king on a chessboard. Remember that a chessboard has $8$ rows and $8$ columns (for the purposes of this problem, both the rows and the columns are numbered $1$ through $8$); let's denote the square in row $r$ and column $c$ by $(r, c)$. A king on a square $(r, c)$ can move to another square $(r', c')$ if and only if $(r'-r)^2+(c'-c)^2 ≤ 2$.

Ada placed her king on the square $(R, C)$. Now, she is counting the number of squares that can be visited (reached) by the king in at most $K$ moves. Help Ada verify her answers.

------  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 and only line of each test case contains three space-separated integers $R$, $C$ and $K$.

------  Output ------
For each test case, print a single line containing one integer — the number of squares the king can visit.

------  Constraints  ------
$1 ≤ T ≤ 512$
$1 ≤ R, C, K ≤ 8$

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

1 3 1
----- Sample Output 1 ------ 
6
----- explanation 1 ------ 
Example case 1: The king can stay on its original square or move to one of the squares circled in the following figure.

Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Graph traversal

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(r, c, k) = map(int, input().split())
	a = min(8, r + k) - max(1, r - k)
	b = min(8, c + k) - max(1, c - k)
	print((a + 1) * (b + 1))


t = int(input())
for _ in range(t):
	(R, C, K) = [int(x) for x in input().split()]
	up = min(8, R + K) - max(1, R - K)
	lr = min(8, C + K) - max(1, C - K)
	print((up + 1) * (lr + 1))


t = int(input())
for _ in range(t):
	(a, b, c) = map(int, input().split())
	x = min(8, a + c) - max(1, a - c)
	y = min(8, b + c) - max(1, b - c)
	print((x + 1) * (y + 1))


t = int(input())
for _ in range(t):
	(r, c, k) = map(int, input().strip().split())
	l = 0
	b = 0
	if r + k > 8:
		a = r + k - 8
		l += k - a
	else:
		l += k
	if r - k < 1:
		a = 1 - (r - k)
		l += k - a
	else:
		l += k
	if c + k > 8:
		a = c + k - 8
		b += k - a
	else:
		b += k
	if c - k < 1:
		a = 1 - (c - k)
		b += k - a
	else:
		b += k
	print((l + 1) * (b + 1))


def moves(x, y, k):
	if k < 0 or x < 1 or y < 1 or (x > 8) or (y > 8):
		return 0
	(u, d) = (x - k, x + k)
	(l, r) = (y - k, y + k)
	if u < 1:
		u = 1
	if d > 8:
		d = 8
	if l < 1:
		l = 1
	if r > 8:
		r = 8
	a = (d - u + 1) * (r - l + 1)
	return a
t = int(input())
while t:
	t -= 1
	(x, y, k) = map(int, input().split())
	print(moves(x, y, k))


def f(r, c, k):
	olist = []
	dx = [-1, -1, -1, 0, 0, 1, 1, 1]
	dy = [-1, 0, 1, -1, 1, -1, 0, 1]
	for i in range(0, 8):
		ilist = []
		for j in range(0, 8):
			ilist.append(0)
		olist.append(ilist)
	pos = []
	ans = 1
	pos.append([r - 1, c - 1])
	olist[r - 1][c - 1] = 1
	while len(pos) and k > 0:
		cnt = len(pos)
		while cnt > 0:
			(i, j) = pos[0]
			pos = pos[1:]
			for l in range(0, 8):
				ni = i + dx[l]
				nj = j + dy[l]
				if ni >= 0 and nj >= 0 and (ni < 8) and (nj < 8) and (olist[ni][nj] == 0):
					ans += 1
					olist[ni][nj] = 1
					pos.append([ni, nj])
			cnt -= 1
		k -= 1
	return ans
t = int(input())
for i in range(0, t):
	(r, c, k) = list(map(int, input().split()))
	print(f(r, c, k))


l = []
cur = []
for i in range(8):
	a = []
	for j in range(8):
		a.append(0)
	l.append(a)
	cur.append(a)

def der(r, c, x, y, k):
	if k <= 0 or r < 0 or c < 0 or (c > 7) or (r > 7):
		return
	else:
		if r == x and c == y:
			l[r][c + 1] = 1
			der(r, c + 1, x, y, k - 1)
			l[r + 1][c] = 1
			der(r + 1, c, x, y, k - 1)
			l[r + 1][c + 1] = 1
			der(r + 1, c + 1, x, y, k - 1)
			l[r - 1][c] = 1
			der(r - 1, c, x, y, k - 1)
			l[r - 1][c + 1] = 1
			der(r - 1, c + 1, x, y, k - 1)
			l[r - 1][c - 1] = 1
			der(r - 1, c - 1, x, y, k - 1)
			l[r][c - 1] = 1
			der(r, c - 1, x, y, k - 1)
			l[r + 1][c - 1] = 1
			der(r + 1, c - 1, x, y, k - 1)
		if r == x and c > y:
			l[r][c + 1] = 1
			der(r, c + 1, x, y, k - 1)
		if r == x and c < y:
			l[r][c - 1] = 1
			der(r, c - 1, x, y, k - 1)
		if c == y and r > x:
			l[r + 1][c] = 1
			der(r + 1, c, x, y, k - 1)
		if c == y and r < x:
			l[r - 1][c] = 1
			der(r - 1, c, x, y, k - 1)
		if c > y and r > x:
			l[r][c + 1] = 1
			der(r, c + 1, x, y, k - 1)
			l[r + 1][c] = 1
			der(r + 1, c, x, y, k - 1)
			l[r + 1][c + 1] = 1
			der(r + 1, c + 1, x, y, k - 1)
		if c > y and r < x:
			l[r][c + 1] = 1
			der(r, c + 1, x, y, k - 1)
			l[r - 1][c] = 1
			der(r - 1, c, x, y, k - 1)
			l[r - 1][c + 1] = 1
			der(r - 1, c + 1, x, y, k - 1)
		if c < y and r < x:
			l[r - 1][c] = 1
			der(r - 1, c, x, y, k - 1)
			l[r - 1][c - 1] = 1
			der(r - 1, c - 1, x, y, k - 1)
			l[r][c - 1] = 1
			der(r, c - 1, x, y, k - 1)
		if c < y and r > x:
			l[r + 1][c] = 1
			der(r + 1, c, x, y, k - 1)
			l[r + 1][c - 1] = 1
			der(r + 1, c - 1, x, y, k - 1)
			l[r][c - 1] = 1
			der(r, c - 1, x, y, k - 1)

def newder(r, c, k):
	if k < 0 or r < 0 or c < 0 or (c > 7) or (r > 7):
		return
	else:
		l[r][c] = 1
		newder(r, c + 1, k - 1)
		newder(r + 1, c, k - 1)
		newder(r + 1, c + 1, k - 1)
		newder(r - 1, c, k - 1)
		newder(r - 1, c + 1, k - 1)
		newder(r - 1, c - 1, k - 1)
		newder(r, c - 1, k - 1)
		newder(r + 1, c - 1, k - 1)
for _ in range(int(input())):
	(r, c, k) = map(int, input().split())
	r = r - 1
	c = c - 1
	ans = (min(7, c + k) - max(0, c - k) + 1) * (min(7, r + k) - max(0, r - k) + 1)
	print(ans)


n = int(input())
for i in range(n):
	lst = list(map(int, input().split()))
	r = lst[0]
	c = lst[1]
	k = lst[2]
	r1 = max(1, r - k)
	r2 = min(8, r + k)
	c1 = max(1, c - k)
	c2 = min(8, c + k)
	ans = r2 - r1 + 1
	ans1 = c2 - c1 + 1
	print(ans * ans1)


T = int(input())
while T > 0:
	(R, C, K) = list(map(int, input().split()))
	count = 0
	i = R - K
	while i <= R + K:
		j = C - K
		while j <= C + K:
			if 0 < i < 9 and 0 < j < 9:
				count += 1
			j += 1
		i += 1
	print(count)
	T -= 1


t = int(input())
for i in range(t):
	(r, c, k) = map(int, input().split())
	visited = []
	g = [[None for i in range(8)] for j in range(8)]
	ans = 0
	for i in range(r - k, r + k + 1):
		for j in range(c - k, c + k + 1):
			if 0 < i < 9 and 0 < j < 9:
				ans += 1
	print(ans)


t = int(input())
for i in range(t):
	(r, c, k) = map(int, input().split())
	x1 = 8 if r + k > 8 else r + k
	y1 = 8 if c + k > 8 else c + k
	x2 = 1 if r - k < 1 else r - k
	y2 = 1 if c - k < 1 else c - k
	print((x1 - x2 + 1) * (y1 - y2 + 1))


for _ in range(int(input())):
	(r, c, k) = map(int, input().split())
	ans = 0
	for i in range(r - k, r + k + 1):
		for j in range(c - k, c + k + 1):
			if 0 < i < 9 and 0 < j < 9:
				ans += 1
	print(ans)


for _ in range(int(input())):
	(Y, X, K) = map(int, input().split())
	l = X - K if X - K > 0 else 1
	r = X + K if X + K < 9 else 8
	u = Y - K if Y - K > 0 else 1
	d = Y + K if Y + K < 9 else 8
	print((r - l + 1) * (d - u + 1))


def check(i, j):
	if i < 0 or i > 7 or j < 0 or (j > 7):
		return False
	return True
t = int(input())
for _ in range(t):
	(r, c, k) = list(map(int, input().split()))
	chess = [[0 for i in range(8)] for j in range(8)]
	chess[r - 1][c - 1] = 1
	q = [(r - 1, c - 1)]
	d = [(1, 0), (0, 1), (0, -1), (-1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]
	while k:
		n = len(q)
		while n:
			(i, j) = q.pop(0)
			for (y, z) in d:
				(ni, nj) = (i + y, j + z)
				if check(ni, nj) and chess[ni][nj] == 0:
					chess[ni][nj] = 1
					q.append((ni, nj))
			n -= 1
		k -= 1
	count = 0
	for i in range(8):
		for j in range(8):
			if chess[i][j]:
				count += 1
	print(count)


for _ in range(int(input())):
	(r, c, k) = map(int, input().split())
	minr = max(1, r - k)
	maxr = min(8, r + k)
	minc = max(1, c - k)
	maxc = min(8, c + k)
	print((maxr - minr + 1) * (maxc - minc + 1))


for _ in range(int(input())):
	(r, c, k) = map(int, input().split())
	r1 = max(r - k, 1)
	r2 = min(r + k, 8)
	c1 = max(c - k, 1)
	c2 = min(c + k, 8)
	print((r2 - r1 + 1) * (c2 - c1 + 1))


t = int(input())
for i in range(t):
	(r, c, k) = map(int, input().split())
	v1 = max(r - k, 1)
	v2 = min(8, r + k)
	h1 = max(c - k, 1)
	h2 = min(c + k, 8)
	print((v2 - v1 + 1) * (h2 - h1 + 1))


for tc in range(1, int(input()) + 1):
	if tc:
		(x, y, k) = list(map(int, input().split()))
		b2 = min(x + k, 8)
		b1 = max(x - k, 1)
		h2 = min(y + k, 8)
		h1 = max(y - k, 1)
		length = b2 - b1 + 1
		breadth = h2 - h1 + 1
		print(length * breadth)


T = int(input(''))
for t in range(T):
	a = list(map(int, input('').strip().split()))
	(r, c, k) = (a[0], a[1], a[2])
	rtl = max(r - k, 1)
	ctl = max(c - k, 1)
	rbr = min(r + k, 8)
	cbr = min(c + k, 8)
	print((rbr - rtl + 1) * (cbr - ctl + 1))


from collections import deque
t = int(input())
while t:
	t -= 1
	res = 1
	(r, c, k) = map(int, input().split())
	(n, m) = (8, 8)
	q = deque([(r, c)])
	s = set()
	s.add((r, c))
	cnt = 1
	dist = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]

	def isSafe(a, b):
		if a >= 1 and a <= 8 and (b >= 1) and (b <= 8):
			return True
		return False
	while q and k != 0:
		if k != 0:
			for _ in range(cnt):
				temp = 0
				(x, y) = q.popleft()
				for (a, b) in dist:
					if (x + a >= 1 and x + a <= 8 and (y + b >= 1) and (y + b <= 8)) and (x + a, y + b) not in s:
						s.add((x + a, y + b))
						res += 1
						q.append((x + a, y + b))
			k -= 1
			cnt = len(q)
	print(res)


nbofcases = int(input())
nbofblocks = 0
for i in range(nbofcases):
	(R, C, K) = [int(x) for x in input().split()]
	right = R + K
	left = R - K
	up = C - K
	down = C + K
	if up <= 0:
		up = 1
	if down > 8:
		down = 8
	if right > 8:
		right = 8
	if left <= 0:
		left = 1
	w = right - left + 1
	l = down - up + 1
	print(w * l)


for _ in range(int(input())):
	(r, c, k) = map(int, input().split())
	left = c - k
	if left <= 0:
		left = 1
	right = c + k
	if right > 8:
		right = 8
	top = r - k
	if top <= 0:
		top = 1
	bottom = r + k
	if bottom > 8:
		bottom = 8
	length = bottom - top + 1
	width = right - left + 1
	print(length * width)


import math
t = int(input())
for j in range(t):
	(r, c, k) = list(map(int, input().split()))
	b2 = min(r + k, 8)
	b1 = max(r - k, 1)
	h2 = min(c + k, 8)
	h1 = max(c - k, 1)
	length = b2 - b1 + 1
	breadth = h2 - h1 + 1
	print(length * breadth)


t = int(input())
for iui in range(t):
	arr = list(map(int, input().split()))
	start = [arr[0] - 1, arr[1] - 1]
	grid = [[0 for k in range(8)] for l in range(8)]
	m = arr[2]
	count = 0
	previous = [start]
	current = []
	for o in range(m):
		for item in previous:
			for i in [-1, 0, 1]:
				for j in [-1, 0, 1]:
					if not (0 <= item[0] + i <= 7 and 0 <= item[1] + j <= 7):
						continue
					if grid[item[0] + i][item[1] + j] == 0:
						grid[item[0] + i][item[1] + j] = 1
						current.append([item[0] + i, item[1] + j])
						count += 1
		previous = current[:]
		current.clear()
	print(count)


t = int(input())
for j in range(t):
	(r, c, k) = map(int, input().split())
	b1 = min(r + k, 8)
	b2 = max(r - k, 1)
	h1 = min(c + k, 8)
	h2 = max(c - k, 1)
	print((b1 - b2 + 1) * (h1 - h2 + 1))


from math import gcd, sqrt, ceil, floor, log10, log2
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
RECURSION_LIMIT = int(10000000.0)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(1000000000.0) + 7
NEWLINE = '\n'
SPACE = ' '
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))
enum = lambda itr: enumerate(itr)

def toposort(graph, n):
	degree = [0] * n
	for node in graph:
		for adj in graph[node]:
			degree[adj] += 1
	bfs_queue = [node for node in range(n) if not degree[node]]
	for node in bfs_queue:
		for adj in graph[node]:
			degree[adj] -= 1
			if not degree[adj]:
				bfs_queue.append(adj)
	return (bfs_queue, degree)

def dfs(graph, node, visited):
	visited.add(node)
	for adj in graph[node]:
		if adj in visited:
			continue
		dfs(graph, adj, visited)

def solve(*args, **kwargs):
	(r, c, k) = args[0]
	visited = set()
	q = deque([(r - 1, c - 1, k)])
	res = k == 1
	while q:
		(x, y, cnt) = q.popleft()
		if not cnt:
			continue
		for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]:
			(nx, ny) = (x + dx, y + dy)
			if 0 <= nx < 8 and 0 <= ny < 8 and ((nx, ny) not in visited):
				visited.add((nx, ny))
				q.append((nx, ny, cnt - 1))
				res += 1
	return res

def main(*args, **kwargs):
	for _ in range(int(input())):
		arg3 = inp_vars(int, SPACE)
		res = solve(*(arg3,))
		if type(res) in {list, tuple, set}:
			print(*res, sep=' ')
		else:
			print(res)
main()


n = int(input())
while n:
	(x, y, k) = map(int, input().split())
	count = 1
	l = [[x - 1, y - 1]]
	while k:
		prev = 0
		for i in range(prev, len(l)):
			x = l[i][0]
			y = l[i][1]
			temp = [[x - 1, y - 1], [x - 1, y], [x - 1, y + 1], [x, y - 1], [x, y + 1], [x + 1, y - 1], [x + 1, y], [x + 1, y + 1]]
			prev = len(l)
			for i in temp:
				if i not in l:
					if i[0] >= 0 and i[0] < 8 and (i[1] >= 0) and (i[1] < 8):
						l.append(i)
		if len(l) == 64:
			break
		k -= 1
	print(len(l))
	n -= 1


t = int(input())
for i in range(t):
	(r, c, k) = map(int, input().split())
	b2 = min(r + k, 8)
	b1 = max(r - k, 1)
	h2 = min(c + k, 8)
	h1 = max(c - k, 1)
	length = b2 - b1 + 1
	breadth = h2 - h1 + 1
	print(length * breadth)


tn = int(input())
for _ in range(tn):
	(r, c, k) = map(int, input().split())
	l1 = min(8, c + k) - max(1, c - k) + 1
	l2 = min(8, r + k) - max(1, r - k) + 1
	print(l1 * l2)


for tc in range(1, int(input()) + 1):
	if tc:
		ans = 0
		(x, y, k) = list(map(int, input().split()))
		for i in range(1, 8 + 1):
			for j in range(1, 8 + 1):
				if max(abs(i - x), abs(j - y)) <= k:
					ans += 1
		print(ans)


def squaresInRange(r, c, k):
	topLeft = [min(8, r + k), max(1, c - k)]
	bottomRight = [max(1, r - k), min(8, c + k)]
	return (abs(topLeft[0] - bottomRight[0]) + 1) * (abs(topLeft[1] - bottomRight[1]) + 1)
testCount = int(input())
for i in range(testCount):
	(r, c, k) = [int(x) for x in input().split()]
	print(squaresInRange(r, c, k))


for t in range(int(input())):
	(r, c, k) = map(int, input().split())
	res = 0
	for i in range(1, 9):
		for j in range(1, 9):
			if max(abs(i - r), abs(j - c)) <= k:
				res += 1
	print(res)


def read_input():
	t = int(input())
	test_cases = []
	for i in range(t):
		test_case = [int(item) for item in input().split()]
		test_cases.append(test_case)
	return (t, test_cases)

def solve_cases(t, test_cases):
	for (r, c, k) in test_cases:
		print(count_squares(r, c, k))

def count_squares(r, c, k):
	visited = set()
	to_visit = {(r, c)}
	for i in range(k):
		to_visit_next = set()
		for (x, y) in to_visit:
			visited.add((x, y))
			for h in range(-1, 2):
				new_x = x + h
				if new_x > 0 and new_x < 9:
					for k in range(-1, 2):
						new_y = y + k
						new_visited = (new_x, new_y)
						if new_y > 0 and new_y < 9 and (new_visited not in visited):
							to_visit_next.add(new_visited)
		to_visit = to_visit_next
	return len(visited.union(to_visit))
(t, test_cases) = read_input()
solve_cases(t, test_cases)


t = int(input())
while t > 0:
	count = 1
	(r, c, k) = map(int, input().split(' '))
	l = min(8, r + k) - max(1, r - k) + 1
	b = min(8, c + k) - max(1, c - k) + 1
	print(l * b)
	t -= 1


t = int(input())
while t > 0:
	(r, c, k) = map(int, input().split())
	count = 0
	for i in range(-k, k + 1):
		for j in range(-k, k + 1):
			x = r + i
			y = c + j
			if x >= 1 and x <= 8 and (y >= 1) and (y <= 8):
				count += 1
	print(count)
	t -= 1


import collections

def Helper(row, col, visited, k):
	Q = collections.deque()
	Q.append((row, col))
	i = 0
	s = 1
	while len(Q) > 0 and k >= 0:
		if i < s:
			i += 1
			(row, col) = Q.popleft()
			if row < 0 or col < 0 or row >= 8 or (col >= 8):
				continue
			if visited[row][col]:
				continue
			visited[row][col] = 1
			Q.append((row - 1, col))
			Q.append((row + 1, col))
			Q.append((row, col - 1))
			Q.append((row, col + 1))
			Q.append((row - 1, col - 1))
			Q.append((row - 1, col + 1))
			Q.append((row + 1, col - 1))
			Q.append((row + 1, col + 1))
		else:
			i = 0
			s = len(Q)
			k -= 1
	return

def function(R, C, K):
	visited = [[0 for i in range(8)] for j in range(8)]
	Helper(R - 1, C - 1, visited, K)
	ans = sum([sum(x) for x in visited])
	return ans

def main():
	T = int(input())
	for index in range(T):
		(R, C, K) = list(map(int, input().split(' ')))
		val = function(R, C, K)
		print(val)
main()


t = int(input())
for _ in range(t):
	(r, c, k) = list(map(int, input().split()))
	dx = min(c + k, 8) - max(c - k, 1) + 1
	dy = min(r + k, 8) - max(r - k, 1) + 1
	print(dx * dy)


def main():
	T = int(input())
	for counter in range(T):
		(r, c, k) = map(int, input().split())
		corner_points = [[min(r + k, 8), min(c + k, 8)], [min(r + k, 8), max(c - k, 1)], [max(r - k, 1), min(c + k, 8)], [max(r - k, 1), max(c - k, 1)]]
		ans = abs(corner_points[0][1] - corner_points[1][1] + 1) * abs(corner_points[1][0] - corner_points[2][0] + 1)
		print(ans)
main()


t = int(input())
for _ in range(t):
	(r, c, k) = map(int, input().split())
	r = r - 1
	c = c - 1
	r_max = r + k if r + k < 8 else 7
	c_max = c + k if c + k < 8 else 7
	r_min = r - k if r - k >= 0 else 0
	c_min = c - k if c - k >= 0 else 0
	print((r_max - r_min + 1) * (c_max - c_min + 1))


adj = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]
num_test_cases = int(input())
for _ in range(num_test_cases):
	(R, C, K) = [int(x) for x in input().split(' ')]
	visited = set([(R, C)])
	frontier = [(R, C, 1)]
	while len(frontier) > 0:
		(curr_r, curr_c, curr_k) = frontier.pop(0)
		dk = curr_k + 1
		for (adj_r, adj_c) in adj:
			(dr, dc) = (curr_r + adj_r, curr_c + adj_c)
			if dr < 1 or 8 < dr or dc < 1 or (8 < dc) or ((dr, dc) in visited):
				continue
			visited.add((dr, dc))
			if dk <= K:
				frontier.append((dr, dc, dk))
	print(len(visited))


T = int(input())
for _ in range(T):
	(r, c, k) = map(int, input().split())
	count = 0
	for i in range(1, 9):
		for j in range(1, 9):
			if max(abs(r - i), abs(c - j)) <= k:
				count += 1
	print(count)


for _ in range(int(input())):
	(r, c, k) = map(int, input().split())
	print((min(c + k, 8) - max(c - k, 1) + 1) * (min(r + k, 8) - max(r - k, 1) + 1))


from queue import deque
t = int(input())
for _ in range(t):
	(r, c, k) = map(int, input().split())
	r = r - 1
	c = c - 1
	direc = [(0, 0), (0, 1), (0, -1), (-1, 0), (1, 0), (1, 1), (-1, -1), (-1, 1), (1, -1)]
	moves = [[0] * 8 for i in range(8)]
	visited = set()
	q = deque()
	q.append((r, c))
	while q:
		(r, c) = q.popleft()
		for d in direc:
			ni = r + d[0]
			nj = c + d[1]
			if 0 <= ni <= 7 and 0 <= nj <= 7 and ((ni, nj) not in visited):
				visited.add((ni, nj))
				moves[ni][nj] = 1 + moves[r][c]
				q.append((ni, nj))
	cnt = 0
	for i in range(len(moves)):
		for j in range(len(moves[0])):
			if moves[i][j] <= k + 1:
				cnt += 1
	print(cnt)


for _ in range(int(input())):
	(row, col, k) = map(int, input().split())
	(l, r, u, d) = (0, 0, 0, 0)
	d = row + k if row + k < 8 else 8
	u = row - k if row - k > 0 else 1
	r = col + k if col + k < 8 else 8
	l = col - k if col - k > 0 else 1
	print(abs(d - u + 1) * abs(r - l + 1))


for _ in range(int(input())):
	(r, c, k) = map(int, input().split())
	top = max(1, r - k)
	bot = min(8, r + k)
	left = max(1, c - k)
	rig = min(8, c + k)
	p = bot - top + 1
	q = rig - left + 1
	m = p * q
	print(m)


t = int(input())
for i in range(t):
	(r, c, k) = map(int, input().split())
	top = max(1, r - k)
	bottom = min(8, r + k)
	right = min(8, c + k)
	left = max(1, c - k)
	print((bottom - top + 1) * (right - left + 1))


def solution(r, c, k):
	ans = 0
	for i in range(1, 9):
		for j in range(1, 9):
			if max(abs(r - i), abs(c - j)) <= k:
				ans += 1
	return ans
t = int(input())
for _ in range(t):
	(r, c, k) = [int(e) for e in input().split()]
	print(solution(r, c, k))


for _ in range(int(input())):
	(r, c, k) = map(int, input().split())
	q = [(r - 1, c - 1)]
	tx = [-1, 1, 0, 0, 1, -1, 1, -1]
	ty = [0, 0, 1, -1, 1, 1, -1, -1]
	a = [[False for _ in range(8)] for _ in range(8)]
	final = 0
	while k >= 0 and q:
		q.append(-1)
		c = 0
		while q[0] != -1:
			t = q.pop(0)
			a[t[0]][t[1]] = True
			c += 1
			for x in range(8):
				txx = t[0] + tx[x]
				tyy = t[1] + ty[x]
				if 0 <= txx < 8 and 0 <= tyy < 8 and (a[txx][tyy] == False):
					q.append((txx, tyy))
					a[txx][tyy] = True
		q.pop(0)
		k -= 1
		final += c
	print(final)


for _ in range(int(input())):
	(r, c, k) = map(int, input().split())
	Row1 = max(r - k, 1)
	Row2 = min(r + k, 8)
	Col1 = max(c - k, 1)
	Col2 = min(c + k, 8)
	print((Row2 - Row1 + 1) * (Col2 - Col1 + 1))


t = int(input())
for _ in range(t):
	(r, c, k) = map(int, input().split())
	sRow = max(r - k, 1)
	eRow = min(r + k, 8)
	sCol = max(c - k, 1)
	eCol = min(c + k, 8)
	print((eRow - sRow + 1) * (eCol - sCol + 1))


t = int(input())
for i in range(t):
	rck = list(map(int, input().split()))
	r = rck[0]
	c = rck[1]
	k = rck[2]
	if c - k < 1:
		left = 1
	else:
		left = c - k
	if c + k > 8:
		right = 8
	else:
		right = c + k
	if r - k < 1:
		top = 1
	else:
		top = r - k
	if r + k > 8:
		bot = 8
	else:
		bot = r + k
	print((right - left + 1) * (bot - top + 1))


def isvalid(x, y):
	if 1 <= x <= 8 and 1 <= y <= 8:
		return True
	else:
		return False
T = int(input())
for _ in range(T):
	(r, c, k) = map(int, input().split())
	xmoves = [1, 1, 1, 0, 0, -1, -1, -1]
	ymoves = [1, 0, -1, 1, -1, 0, -1, 1]
	distance = [[9 for i in range(9)] for i in range(9)]
	visited = [[0 for _i in range(9)] for i in range(9)]
	idx = 0
	L = [(r, c)]
	visited[r][c] = 1
	distance[r][c] = 0
	while idx < len(L):
		current_distance = distance[L[idx][0]][L[idx][1]]
		for i in range(8):
			x = L[idx][0] + xmoves[i]
			y = L[idx][1] + ymoves[i]
			if isvalid(x, y):
				if not visited[x][y]:
					visited[x][y] = 1
					L.append((x, y))
					distance[x][y] = current_distance + 1
		idx += 1
	ans = 0
	for i in range(1, 9):
		for j in range(1, 9):
			if distance[i][j] <= k:
				ans += 1
	print(ans)


for _ in range(int(input())):
	(r, c, m) = map(int, input().split())
	t = r - m if r - m >= 1 else 1
	b = r + m if r + m < 8 else 8
	l = c - m if c - m >= 1 else 1
	r = c + m if c + m < 8 else 8
	print((b - t + 1) * (r - l + 1))