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