Chef likes rectangles. Among all possible rectangles, he loves rectangles that can be drawn like a grid, such that they have N rows and M columns. Grids are common in Byteland. Hence, Chef has drawn such a rectangle and plans on moving around in it.

The rows of the rectangle are labeled from 1 to N from top to bottom. The columns of the rectangle are labeled form 1 to M from left to right. Thus, the cell in the top left can be denoted by (1,1). The 5^{th} cell from the left in the 4^{th} row form the top can be denoted by (4,5). The bottom right cell can be denoted as (N,M).

Chef wants to move from the cell in the top left to the cell in the bottom right. In each move, Chef may only move one cell right, or one cell down. Also, Chef is not allowed to move to any cell outside the boundary of the rectangle.

Of course, there are many ways for Chef to move from (1,1) to (N,M). Chef has a curious sport. While going from (1,1) to (N,M), he drops a stone on each of the cells he steps on, except the cells (1,1) and
(N,M). Also, Chef repeats this game exactly K times.

Let us say he moved from (1,1) to (N,M), exactly K times. At the end of all the K journeys, let the number of stones, in the cell with the maximum number of stones, be equal to S. Chef wants to know what is the smallest possible value for S.

------ Input ------ 

The first line contains single integer T, the number of test cases. Each of the next T lines contains 3 integers N, M and K, respectivily.

------ Output ------ 

For each test case, output the smallest value possible for S, if the Chef chooses the K paths smartly.

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

1 ≤ T ≤ 100
1 ≤ N, M, K ≤ 70

----- Sample Input 1 ------ 
3
2 2 1
3 3 2
1 5 12
----- Sample Output 1 ------ 
1
1
12
----- explanation 1 ------ 
Test Case 1: Chef may choose any way. The maximum value on any cell would be 1.
Test Case 2: If Chef selects two paths that have a common cell, such as
(1,1)->(1,2)->(2,2)->(3,2)->(3,3)
(1,1)->(2,1)->(2,2)->(3,2)->(3,3)
Then the value of S will be equal to 2, since the number of stones in (2,2) and (3,2) is equal to 2. But, if Chef selects two paths which do not have any common cells, such as
(1,1)->(1,2)->(1,3)->(2,3)->(3,3)
(1,1)->(2,1)->(3,1)->(3,2)->(3,3)
Then the value of S will be equal to 1.

Difficulty: MEDIUM
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
import math
for _ in range(int(input())):
	(n, m, k) = [int(x) for x in input().split(' ')]
	if (n == 1 or m == 1) and (n > 2 or m > 2):
		print(k)
	elif (n == 1 or m == 1) and (n <= 2 or m <= 2):
		print(0)
	else:
		print(math.ceil(k / 2))


from math import ceil
for _ in range(int(input())):
	(rows, cols, k) = map(int, input().split())
	(cols, rows) = (max(rows, cols), min(rows, cols))
	if rows == 1 and cols <= 2:
		print(0)
	elif rows == 1:
		print(k)
	else:
		print(ceil(k / 2))


t = int(input())
import math
for i in range(t):
	(N, M, K) = map(int, input().split())
	if N + M <= 3:
		print(0)
	elif N == 1 or M == 1:
		print(K)
	else:
		print(math.ceil(K / 2))


from math import *
for i in range(int(input())):
	(n, m, k) = map(int, input().split())
	if n + m <= 3:
		print(0)
	elif n == 1 or m == 1:
		print(k)
	else:
		print(ceil(k / 2))


import math
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	if n + m <= 3:
		print(0)
	elif n == 1 or m == 1:
		print(k)
	else:
		print(math.ceil(k / 2))


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	if n + m <= 3:
		print(0)
	elif n == 1 or m == 1:
		print(k)
	elif k % 2 == 1:
		print((k + 1) // 2)
	else:
		print(k // 2)


import math
t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	if n == 1 and m == 2 or (n == 2 and m == 1):
		print(0)
	elif m == 1 or n == 1:
		print(k)
	else:
		print(math.ceil(k / 2))


t = int(input())
for _ in range(t):
	(n, m, k) = list(map(int, input().split()))
	if min(n, m) == 1 and max(n, m) > 2:
		print(k)
	elif max(n, m) == 1 or (min(n, m) == 1 and max(n, m) == 2):
		print(0)
	elif k % 2 == 0:
		print(k // 2)
	else:
		print(k // 2 + 1)


import math as m
t = int(input())
for _ in range(t):
	(r, c, k) = list(map(int, input().split(' ')))
	if r > c:
		temp = r
		r = c
		c = temp
	if r == 1 and (c == 2 or c == 1):
		print('0')
		continue
	if r == 1:
		print(k)
		continue
	print(m.ceil(k / 2))


for i in range(int(input())):
	(a, b, k) = map(int, input().split())
	if a - 1 + b - 1 <= 1:
		print(0)
	elif a == 1 or b == 1:
		print(k)
	else:
		print((k + 1) // 2)


t = int(input())
for _ in range(0, t):
	(n, m, k) = map(int, input().split())
	if n + m <= 3:
		print(0)
		continue
	if min(n, m) == 1:
		print(k)
	else:
		print((k + 1) // 2)


n = int(input())
for i in range(n):
	(N, M, K) = map(int, input().split())
	if N + M <= 3:
		print(0)
	elif M == 1 or N == 1:
		print(K)
	elif K % 2 == 0:
		print(K // 2)
	else:
		print((K + 1) // 2)


t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	if min(n, m) == 1:
		if max(n, m) <= 2:
			print(0)
			continue
		else:
			print(k)
			continue
	print((k + 1) // 2)


import math
for i in range(int(input())):
	(a, b, c) = map(int, input().split())
	if a == 1 and b == 2 or (b == 1 and a == 2):
		print(0)
	elif a == 1 or b == 1:
		print(c)
	elif c <= 2:
		print(1)
	else:
		print(math.ceil(c / 2))


z = int(input())
for j in range(0, z):
	(a, b, k) = list(map(int, input().split()))
	if a == 1 and b == 1 or (a == 1 and b == 2) or (a == 2 and b == 1):
		print(0)
	elif a == 1 or b == 1:
		print(k)
	else:
		print(k // 2 + k % 2)


import math
tests = int(input())
for i in range(tests):
	(rows, cols, k) = map(int, input().split())
	if rows == 2 and cols == 1 or (cols == 2 and rows == 1):
		print(0)
	elif rows == 1 or cols == 1:
		print(k)
	else:
		print(math.ceil(k / 2))


for _ in range(int(input())):
	n = [int(x) for x in input().split()]
	if n[0] == 1 and n[1] == 2 or (n[0] == 2 and n[1] == 1):
		print(0)
	elif n[0] == 1 or n[1] == 1:
		print(n[2])
	elif n[2] == 1:
		print(1)
	elif n[0] > 1 or n[1] > 1:
		print(max(n[2] // 2, n[2] - n[2] // 2))


import math
T = int(input())
while T:
	(n, m, k) = [int(i) for i in input().split(' ')]
	if n + m <= 3:
		print(0)
	elif n == 1 or m == 1:
		print(k)
	else:
		print(math.ceil(k / 2))
	T -= 1


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	ans = 1
	if n == 1 and m == 2 or (n == 2 and m == 1):
		ans = 0
	elif n == 1 or m == 1:
		ans = k
	else:
		ans = (k + 1) // 2
	print(ans)


from math import *
for _ in range(int(input())):
	(N, M, K) = map(int, input().split())
	if N + M <= 3:
		print(0)
	elif N == 1 or M == 1:
		print(K)
	else:
		print(ceil(K / 2))


t = input()
for c in range(0, int(t)):
	(N, M, k) = map(int, input().split())
	if N + M <= 3:
		print(0)
	elif N == 1 or M == 1:
		print(k)
	elif k % 2:
		print((k + 1) // 2)
	else:
		print(k // 2)


import math
t = int(input())
while t > 0:
	t -= 1
	arr = list(map(int, input().split(' ')))
	if arr[0] + arr[1] <= 3:
		print('0')
	elif arr[0] == 1 or arr[1] == 1:
		print(arr[2])
	else:
		print(math.ceil(arr[2] / 2))


for _ in range(int(input())):
	(N, M, K) = [int(s) for s in input().split()]
	if N * M <= 2:
		print(0)
	elif N == 1 or M == 1:
		print(K)
	else:
		print(K - K // 2)


import math
t = int(input())
while t:
	(n, m, k) = list(map(int, input().split()))
	if n + m <= 3:
		print(0)
	elif n == 1 or m == 1:
		print(k)
	else:
		print(math.ceil(k / 2))
	t -= 1


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	if n == 1 and m == 1:
		print(0)
		continue
	if n == 1 and m == 2 or (n == 2 and m == 1):
		print(0)
		continue
	if n == 1 or m == 1:
		print(k)
		continue
	if k % 2 == 0:
		print(k // 2)
	else:
		print(k // 2 + 1)


listInput = lambda : list(map(int, input().split(' ')))
mapInput = lambda : map(int, input().split(' '))
from math import ceil
for _ in range(int(input())):
	(n, m, k) = mapInput()
	if n == 1 and m == 1 or (n == 1 and m == 2) or (n == 2 and m == 1):
		print(0)
	elif n == 1 or m == 1:
		print(k)
	else:
		print(ceil(k / 2))


t = int(input(''))
while t > 0:
	(n, m, k) = map(int, input().split())
	if n == 1 and m == 1:
		print(0)
	elif n == 1 and m == 2:
		print(0)
	elif n == 2 and m == 1:
		print(0)
	elif n == 1 or m == 1:
		print(k)
	elif k % 2 == 0:
		print(k // 2)
	else:
		print(k // 2 + 1)
	t = t - 1