Read problems statements in Mandarin Chinese  and Russian. 

There are S sine functions and C cosine functions as following:
a_{i} sin(2^{i} x), 0 ≤ x ≤ 2π, for i = 0, 1, ..., S−1,b_{j} cos(2^{j} x), 0 ≤ x ≤ 2π, for j = 0, 1, ..., C−1,
where a_{i}, b_{j} are some positive constants (and note that the answer of this problem does not depend on a_{i} and b_{j}).
For example, the following figures show the case of S = 2, C = 0 and the case of S = 3, C = 2.

This figure shows the case of S = 2, C = 0. There are two sine functions a_{1} sin(x) denoted by the red line, and a_{2} sin(2x) denoted by the blue line.

This figure shows the case of S = 3, C = 2. There are five functions a_{1} sin(x), a_{2} sin(2x), a_{3} sin(4x), b_{1} cos(x) and b_{2} cos(2x). In the figure, three sine functions are denoted by blue lines, and two cosine functions are denoted by red lines.
Chef wants to find the number of the points on the x-axis such that at least K functions through the points.

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

The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow.
Each test case contains one line. The line contains three space-separated integers S, C, K.

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

For each test case, print the number of the points on the x-axis such that at least K functions through the points.

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

$1 ≤ T ≤ 200$

Subtask 1: 15 points

$0 ≤ S ≤ 12$
$0 ≤ C ≤ 12$
$1 ≤ K ≤ 25$

Subtask 2: 30 points

$0 ≤ S ≤ 50$
$C = 0$
$1 ≤ K ≤ 50$

Subtask 3: 25 points

$0 ≤ S ≤ 50$
$0 ≤ C ≤ 50$
$K = 1$

Subtask 4: 30 points

$0 ≤ S ≤ 50$
$0 ≤ C ≤ 50$
$1 ≤ K ≤ 100$

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

2 0 1

2 0 2

3 2 1

3 2 3
----- Sample Output 1 ------ 
5

3

9

5
----- explanation 1 ------ 
Example 1. This is the case of S = 2, C = 0. So the situation is the same as the first figure in the statement. There are 5 points on the x-axis such that at least 1 function through the points. That is, x = 0, ?/2, ?, 3?/2, 2?.
Example 2. This is also the case of S = 2, C = 0. So the situation is the same as the first figure in the statement. There are 3 points on the x-axis such that at least 2 functions through the points. That is, x = 0, ?, 2?.
Example 3. This is the case of S = 3, C = 2. So the situation is the same as the second figure in the statement. There are 9 points on the x-axis such that at least 1 function through the points. That is, x = 0, ?/4, ?/2, 3?/4, ?, 5?/4, 3?/2, 7?/4, 2?.
Example 4. This is the case of S = 3, C = 2. So the situation is the same as the second figure in the statement. There are 5 points on the x-axis such that at least 3 functions through the points. That is, x = 0, ?/2, ?, 3?/2, 2?. For example, three sine function through the point x = 0, and two sine functions and one cosine function through the point x = ?/2.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Geometry

Mathematics

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(s, c, k) = map(int, input().split())
	ans = 0
	if s >= k:
		ans = pow(2, s - k + 1) + 1
		if c > s - k:
			ans += pow(2, s - k + 1)
			if k == 1:
				ans += sum((pow(2, r) for r in range(s - k + 2, c + 1)))
	elif k == 1:
		ans += pow(2, c + 1) - 2
	print(ans)


def f2(s, c, k):
	(rows, cols) = (pow(2, max(s + 1, c + 1)) + 1, max(s, c))
	(a, size, count) = ([[0 for x in range(cols)] for y in range(rows)], (rows - 1) / 2, 0)
	for x in range(s):
		y = 0
		while y < rows:
			a[int(y)][int(x)] += 1
			y += size
		size /= 2
	size = (rows - 1) / 2
	for x in range(c):
		y = size / 2
		while y < rows:
			a[int(y)][int(x)] += 1
			y += size
		size /= 2
	for y in a:
		if sum(y) >= k:
			count += 1
	return count
for _ in range(int(input())):
	(s, c, k) = map(int, input().split())
	ans = 0
	if s >= k:
		ans = pow(2, s - k + 1) + 1
		if c > s - k:
			ans += pow(2, s - k + 1)
			if k == 1:
				ans += sum((pow(2, r) for r in range(s - k + 2, c + 1)))
	elif k == 1:
		ans += pow(2, c + 1) - 2
	print(ans)


import sys

def power(a, n):
	r = 1
	c = a
	while n:
		if n & 1:
			r = r * c
		n >>= 1
		c = c * c
	return r
t = int(input())

def f2(s, c, k):
	rows = power(2, max(s + 1, c + 1)) + 1
	cols = max(s, c)
	a = [[0 for x in range(cols)] for y in range(rows)]
	size = (rows - 1) / 2
	for x in range(s):
		y = 0
		while y < rows:
			a[int(y)][int(x)] += 1
			y += size
		size /= 2
	size = (rows - 1) / 2
	for x in range(c):
		y = size / 2
		while y < rows:
			a[int(y)][int(x)] += 1
			y += size
		size /= 2
	count = 0
	for y in a:
		if sum(y) >= k:
			count += 1
	return count
while t:
	line = input().split()
	s = int(line[0])
	c = int(line[1])
	k = int(line[2])
	ans = 0
	if s >= k:
		ans = power(2, s - k + 1) + 1
		if c > s - k:
			ans += power(2, s - k + 1)
			if k == 1:
				ans += sum((power(2, r) for r in range(s - k + 2, c + 1)))
	elif k == 1:
		ans += power(2, c + 1) - 2
	sys.stdout.write(str(ans) + '\n')
	t -= 1


tests = int(input())
for t in range(tests):
	(s, c, k) = map(int, input().split())
	n = [0] * (s + 2)
	for i in range(1, s):
		n[i] = 2 ** (s - i)
	if s > 0:
		n[s] = 3
	for i in range(0, c):
		if i < s - 1:
			n[s - i] += n[s - i - 1]
			n[s - i - 1] = 0
		else:
			n[1] += 2 ** (i + 1)
	print(sum(n[k:]))


__author__ = 'AYUSH'
t = int(input())
for i in range(t):
	(s, c, k) = map(int, input().split())
	ans = 0
	if k == 1:
		if s == 0:
			l = [2 ** r for r in range(1, c + 1)]
			ans = sum(l)
		elif c + 1 > s and c > 0:
			ans = 2 ** s + 1
			l = [2 ** r for r in range(s, c + 1)]
			ans = sum(l, ans)
		elif s >= c + 1 and s > 0:
			ans = 2 ** s + 1
	if k > 1:
		if c == 0:
			if k < s + 1:
				ans = 2 ** (s - k + 1) + 1
		if s == 0:
			ans = 0
		elif s > 0 and c > 0 and (k <= s):
			if c < s - k + 1:
				ans = 2 ** (s - k + 1) + 1
			elif c >= s - k + 1:
				ans = 2 ** (s - k + 2) + 1
	print(ans)


t = int(input())
for i in range(t):
	(s, c, k) = map(int, input().split())
	if k == 1:
		if s == 0:
			counter = 0
		else:
			counter = 3
		if c >= s:
			for k in range(1, c + 1):
				counter += 2 ** k
		else:
			for k in range(1, s):
				counter += 2 ** k
		print(counter)
	elif k > s and k != 1:
		print(0)
	else:
		if s == 0:
			counter = 0
		else:
			counter = 3
		temp = s - 1
		nc = 1
		cb = c
		for sb in range(1, s):
			if cb == 0:
				nc = 0
			if temp + nc >= k:
				counter += 2 ** sb
				temp -= 1
				cb -= 1
		print(counter)


t = int(input())
for _ in range(t):
	(s, c, k) = map(int, input().split())
	ansc = 0
	anss = 0
	if s >= k:
		anss = 2 * 2 ** (s - k) + 1
	if c > s - k and s != 0 and (c > 0) and (s >= k):
		ansc = 2 * 2 ** (s - k)
	if s == 0 and k == 1:
		ansc = 2 * (2 ** c - 1)
	if k == 1 and s < c and (s != 0):
		ansc = 2 ** (s - k + 1) * (2 ** (c - s + k) - 1)
	print(int(anss + ansc))


t = int(input())
pwr2 = [1]
for i in range(1, 52):
	pwr2.append(pwr2[-1] * 2)
for it in range(t):
	good_points = 0
	(s, c, k) = [int(word) for word in input().split()]
	if s >= k:
		good_points += 3
	for i in range(1, max(c + 1, s)):
		soids = 0
		if i <= s - 1:
			soids += s - i
		if i <= c:
			soids += 1
		if soids >= k:
			good_points += pwr2[i]
	print(good_points)


for _ in range(int(input())):
	(S, C, K) = map(int, input().split())
	if K == 1:
		print((1 << max(S, C + 1)) + 1 if S else (1 << C) - 1 << 1)
	elif K <= S and K - 1 + C >= S:
		print((1 << S - K + 2) + 1)
	elif K <= S:
		print((1 << S - K + 1) + 1)
	else:
		print(0)


tt = int(input())
while tt:
	s = 0
	(a, k, c) = map(int, input().split())
	if c == 0:
		s = 0
	elif c > a + k:
		s = 0
	elif c == 1:
		if a > k + 1:
			for i in range(1, a):
				s = s + (1 << i)
			s = s + 3
		else:
			for i in range(1, k + 1):
				s = s + (1 << i)
			if a == 0:
				s = s
			else:
				s = s + 3
	else:
		for i in range(c, a):
			s = s + (1 << a - i)
		if k == 0:
			s = s + 3
		elif a == 0:
			s = 0
		elif c <= a:
			if c >= a - k + 1:
				s = s + 3 + (1 << a - c + 1)
			else:
				s = s + 3
		else:
			s = 0
	print(s)
	tt -= 1


import sys
cos_i = [2 ** (i + 1) for i in range(50)]
sin_i = [2 ** (i + 1) + 1 for i in range(50)]
for _ in range(int(sys.stdin.readline())):
	(S, C, K) = map(int, sys.stdin.readline().split())
	k_pts = [0 for _ in range(K + 1)]
	if S - 1 >= 0:
		k_pts[1] = sin_i[S - 1] + sum(cos_i[S - 1:C])
	else:
		k_pts[1] = sum(cos_i[0:C])
	for i in range(2, K + 1):
		if S - i >= 0:
			if S - i < C:
				k_pts[i] = sin_i[S - i + 1]
			else:
				k_pts[i] = sin_i[S - i]
	print(k_pts[K])


t = int(input())
for test in range(t):
	(s, c, k) = [int(it) for it in input().split()]
	points = []
	for ss in range(s):
		for item in points:
			item[1] += 1
		points.append([2 ** ss if ss else 3, 1])
		if ss - 1 in range(c):
			points[-1][1] += 1
	for cc in range(s - 1 if s else 0, c):
		points.append([2 ** (cc + 1), 1])
	res = 0
	for item in points:
		if item[1] >= k:
			res += item[0]
	print(res)


__author__ = 'sanjay'
import sys

def count_num_S_C(s, k):
	if k == 1:
		return 2 * pow(2, s) + 1
	else:
		return pow(2, s - k + 2) + 1

def count_num_C(s, c, k):
	if k == 1:
		return pow(2, c + 1) + 1
	else:
		return pow(2, s - k + 2) + 1

def count_num_S(s, c, k):
	if k <= s - c:
		return pow(2, s - k + 1) + 1
	else:
		return pow(2, s - k + 2) + 1
test = int(input())
while test:
	test -= 1
	(s, c, k) = map(int, sys.stdin.readline().split(' '))
	if s < 0 or c < 0 or (s - k < 0 and c - k < 0):
		print(0)
	elif s - k < 0 and k > 1:
		print(0)
	elif s == 0:
		if k == 1:
			print(pow(2, c + 1) - 2)
		else:
			print(0)
	elif c == 0:
		print(pow(2, s - k + 1) + 1)
	elif s > c:
		print(count_num_S(s, c, k))
	elif c > s:
		print(count_num_C(s, c, k))
	elif s == c:
		print(count_num_S_C(s, k))
sys.exit(0)


for i in range(int(input())):
	(S, C, K) = map(int, input().split())
	if K > S + C:
		print(0)
	elif K == 1:
		if S == 0:
			print(2 * (2 ** C - 1))
		elif S > C:
			print(2 ** S + 1)
		else:
			print(2 ** S + 2 ** S * (2 ** (C - S + 1) - 1) + 1)
	elif S == 0 or K > S:
		print(0)
	elif C >= S - K + 1:
		print(2 ** (S - K + 2) + 1)
	else:
		print(2 ** (S - K + 1) + 1)


for i in range(int(input())):
	(s, c, k) = [int(x) for x in input().split()]
	if s == 0 and k == 1:
		print(2 ** (c + 1) - 2)
		continue
	if k > s:
		print(0)
		continue
	if k == 1:
		if s > c:
			x = s
		else:
			x = c + 1
	elif s >= c + k:
		x = max(s, c) + 1 - k
	elif s < c:
		x = s + 2 - k
	else:
		x = max(s, c) + 2 - k
	print(2 ** x + 1)


T = int(input())
for _ in range(0, T):
	(S, C, K) = map(int, input().split())
	if C == 0:
		if K <= S:
			print(pow(2, S - K + 1) + 1)
		else:
			print('0')
	elif K == 1:
		if S > C:
			print(pow(2, S) + 1)
		elif S == C:
			print(pow(2, S) + 1 + pow(2, C))
		elif S != 0:
			print(pow(2, S) + 1 + pow(2, S) * (pow(2, C - S + 1) - 1))
		else:
			print(2 * (pow(2, C) - 1))
	elif S >= K:
		if C < S - K + 1:
			print(pow(2, S - K + 1) + 1)
		else:
			print(2 * pow(2, S - K + 1) + 1)
	else:
		print('0')


import math
val = [0]
for i in range(1, 52):
	val.append(pow(2, i) + 1)
t = int(input())
for test in range(1, t + 1):
	(s, c, k) = list(map(int, input().split()))
	if s == 0 and c == 0:
		ans = 0
	elif s == 0 and k == 1:
		ans = pow(2, c + 1) - 2
	elif s == 0 and k > 1:
		ans = 0
	elif k > s:
		ans = 0
	elif c == 0:
		ans = val[s - k + 1]
	elif c > s and k == 1:
		ans = val[c + 1]
	elif s - k < c:
		ans = val[s - k + 2]
	else:
		ans = val[s - k + 1]
	print(ans)


n = int(input())
while n:
	n -= 1
	(a, b, c) = map(int, input().split())
	sum = 0
	for i in range(c, a):
		sum = sum + 2 ** (a - i)
	if c == 0:
		print(0)
	elif c > a + b:
		print(0)
	elif c == 1:
		sum = 0
		if a > b + 1:
			for i in range(1, a):
				sum += 2 ** i
			print(sum + 3)
		else:
			for i in range(1, b + 1):
				sum += 2 ** i
			if a == 0:
				print(sum)
			else:
				print(sum + 3)
	elif b == 0:
		print(sum + 3)
	elif a == 0:
		print(0)
	elif c <= a:
		if c >= a - b + 1:
			sum = sum + 3 + 2 ** (a - c + 1)
		else:
			sum += 3
		print(sum)
	else:
		print(0)


def sinZeros(i, denPow):
	multiplier = 2 ** (denPow - i)
	ans = []
	for k in range(0, 2 ** (i + 2) + 1, 2):
		ans.append(multiplier * k)
	return ans

def cosZeros(i, denPow):
	multiplier = 2 ** (denPow - i)
	ans = []
	for k in range(1, 2 ** (i + 2), 2):
		ans.append(multiplier * k)
	return ans

def bruteforce(s, c, k):
	denPow = max(c, s) - 1
	hits = [0 for i in range(2 ** (denPow + 2) + 1)]
	for i in range(s):
		for x in sinZeros(i, denPow):
			hits[x] += 1
	for i in range(c):
		for x in cosZeros(i, denPow):
			hits[x] += 1
	ans = 0
	for x in hits:
		if x >= k:
			ans += 1
	return ans

def c0(s, k):
	if s < k:
		return 0
	return 2 ** (s + 1 - k) + 1

def k1(s, c):
	if s == 0 and c == 0:
		return 0
	if c == 0:
		return c0(s, 1)
	if s == 0:
		return 2 ** (c + 1) - 2
	if c < s:
		return c0(s, 1)
	else:
		return 3 + k1(0, c)

def f(s, c, k):
	if k == 1:
		return k1(s, c)
	if s < k:
		return 0
	if k > 2:
		return f(s - 1, c, k - 1)
	elif c == 0:
		return c0(s, k)
	elif s - c >= 2:
		return c0(s, k)
	else:
		return c0(s + 1, k)

def test(N, K):
	for k in range(1, K + 1):
		for s in range(N):
			row = []
			for c in range(N):
				row.append(str(bruteforce(s, c, k)))
			print('\t'.join(row))
		print()

def test2(N, K):
	for k in range(1, K + 1):
		for s in range(N):
			row = []
			for c in range(N):
				row.append(str(f(s, c, k)))
			print('\t'.join(row))
		print()

def test3(N, K):
	for k in range(1, K + 1):
		for s in range(N):
			for c in range(N):
				x = bruteforce(s, c, k)
				y = f(s, c, k)
				if x != y:
					print(k, s, c, '--', x, y)
					while True:
						x = 1

def main():
	T = eval(input())
	for t in range(T):
		(s, c, k) = [eval(x) for x in input().split()]
		if s <= 12 and c <= 12 and (k <= 25):
			print(bruteforce(s, c, k))
		elif s <= 50 and c == 0 and (k <= 50):
			print(c0(s, k))
		elif s <= 50 and c <= 50 and (k == 1):
			print(k1(s, c))
		else:
			print(f(s, c, k))
main()