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.

见题面

见题面