You have an N \times M grid consisting of N rows numbered 1 to N from top to bottom and M columns numbered 1 to M from left to right. Each cell of the grid is initially white.

You can perform the following operation any number of times (possibly zero):
Select a row i (1 ≤ i ≤ N) and paint all the cells in row i black.
Or select a column i (1 ≤ i ≤ M) and paint all the cells in column i black.

Note that cells which are already black remain black if they are painted over again.

Determine if it is possible to paint exactly K cells of the grid black after performing some operations.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line containing N, M and K — the number of rows, the number of columns and the number of cells to paint black.

------ Output Format ------ 

For each test case, output the string YES if it is possible to paint exactly K cells black, and NO if it is not.

You may print each character of YES and NO in uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).

------ Constraints ------ 

$1 ≤ T ≤ 2000$
$3 ≤ N, M ≤ 10^{9}$
$0 ≤ K ≤ 10^{9}$

----- Sample Input 1 ------ 
2
3 5 13
3627 17424 27008005
----- Sample Output 1 ------ 
YES
NO
----- explanation 1 ------ 
Test case 1: One possible sequence of operations is as follows:
- Select column $2$ and paint it black.
- Select row $1$ and paint it black.
- Select column $4$ and paint it black.
- Select column $5$ and paint it black.
- Select row $3$ and paint it black.

After performing these operations, the grid contains exactly $13$ black cells. Hence the answer is YES.

Difficulty: VERY_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
import math
t = int(input())
for i in range(t):
	(n, m, k) = tuple(map(int, input().split()))
	paint = False
	less = min(n, m)
	more = max(n, m)
	if k == 0:
		paint = True
	elif k == n * m:
		paint = True
	elif 0 < k < n * m:
		rows = 0
		while rows < less:
			rem = k - rows * more
			if rem < 0:
				break
			if rem % (less - rows) == 0:
				paint = True
				break
			rows += 1
	if paint == True:
		print('YES')
	elif paint == False:
		print('NO')


def check(n, m, k):
	x = 0
	while x <= n and x * x <= k:
		rem = k - x * m
		if rem < 0:
			break
		if x == n:
			if rem == 0:
				return True
		else:
			y = rem // (n - x)
			if y <= m and y * (n - x) == rem:
				return True
		x += 1
	return False
t = int(input())
for _ in range(t):
	(n, m, k) = [int(x) for x in input().split()]
	ans = check(n, m, k) or check(m, n, k)
	if ans:
		print('YES')
	else:
		print('NO')


T = int(input())
for testNum in range(T):
	(N, M, K) = list(map(int, input().split(' ')))
	possible = M * N == K
	if M * N > K:
		while not possible and K > 0 and (M > 0):
			possible = K % M == 0
			M = M - 1
			K = K - N
	if possible or K == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(m, n, k) = map(int, input().split())
	if k > m * n:
		print('NO')
		continue
	if k == m * n:
		print('YES')
		continue
	i = 1
	pos = False
	for y in range(min(n, k // m) + 1):
		if (k - y * m) % (n - y) == 0:
			x = (k - y * m) // (n - y)
			if 0 <= x <= m:
				pos = True
				break
	print('YES' if pos else 'NO')


n = int(input())
for j in range(0, n):
	(n, m, k) = list(map(int, input().split()))
	if n * m < k:
		print('NO')
	else:
		flag = 0
		if m < n:
			for i in range(0, int(k // n) + 1):
				if (k - n * i) % (m - i) == 0:
					print('YES')
					flag = -1
					break
			if flag == 0:
				print('NO')
		else:
			for i in range(0, k // m + 1):
				if (k - m * i) % (n - i) == 0:
					print('YES')
					flag = -1
					break
			if flag == 0:
				print('NO')