Question is quite straightforward. Given a point A(a, b), you need to find number of points P(x, y) having Manhattan distance less than or equal to k from the given point A. Here, a, b, x and y are integers.
Manhattan distance between two points (x1, y1) and (x2, y2) is considered as abs(x1 - x2) + abs(y1 - y2), where abs(x) is the absolute value of x.
See the sample case for better understanding.
Input format:
First line contains an integer T, denoting the number of test-cases.
Next T lines contain three integers a, b and k, representing the given point A(a, b) and distance k.
Output format:
For each testcase, print the number of possible points P.
Constraints:
1 <= T <= 1000000
0 <= a, b, k <= 1000000000(1e9)
Subtasks:
Subtask #1 (10 points) : 1 <= T <= 10, 0 <= a, b, k <= 1000
Subtask #2 (10 points) : 1 <= T <= 10, 0 <= a, b, k <= 1000000
Subtask #3 (10 points) : 1 <= T <= 10, 0 <= a, b, k <= 1000000000
Subtask #4 (20 points) : 1 <= T <= 1000000, 0 <= a, b, k <= 1000
Subtask #5 (50 points) : Original Constraints
In first testcase, only one point P(2, 3) is at a distance less than or equal to 0 from A(2, 3).
In second testcase, following five points are at a distance less than or equal to 1 from A(0,0) :-
P(0,0) --> Distance = 0
P(1,0) --> Distance = 1
P(0,1) --> Distance = 1
P(-1,0) --> Distance = 1
P(0,-1) --> Distance = 1
Hence, answer is 5.
