Sign Wave

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
There are S sine functions and C cosine functions as following:
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 xaxis 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 spaceseparated integers S, C, K.
Output
For each test case, print the number of the points on the xaxis such that at least K functions through the points.
Constraints and Subtasks
 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
Example
Input: 4 2 0 1 2 0 2 3 2 1 3 2 3 Output: 5 3 9 5
Explanation
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 xaxis 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 xaxis 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 xaxis 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 xaxis 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.
Author:  chandubaba 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/SIGNWAVE 
Tags  chandubaba, march15, simple, trigonometry 
Date Added:  6012015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 