E. Extradimensional Cosmic Phenomenon
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Intergalactic Cosmic Phenomenon Containment (ICPC) has reported a surge in Breach-Level Unstable Events (BLUEs) — rare extradimensional disturbances that manifest as rift points in local spacetime. If left unchecked, these anomalies may cascade into a full-scale reality fracture, erasing the timeline of the entire universe.

To address this crisis, the ICPC has deployed $$$N$$$ Anomaly Regulation Centers (ARCs). Each ARC must be assigned a set of BLUEs to stabilize, under the following conditions:

  • There are $$$X$$$ Type-Alpha BLUEs, each requiring exactly 1 unit of energy to stabilize.
  • There are $$$Y$$$ Type-Omega BLUEs, each requiring exactly 2 units of energy to stabilize.

Each BLUE must be assigned entirely to exactly one ARC (no splitting or sharing). An ARC may stabilize multiple BLUEs, but the total required energy for its assigned anomalies must be drawn from its own reservoir.

To maintain synchronization across containment protocols, the ICPC mandates that the energy loads be distributed as evenly as possible among the ARCs.

Your task is to determine the minimum possible energy imbalance, defined as the difference between the maximum energy assigned to any ARC and the minimum energy assigned to any ARC.

Input

The first line contains a single integer $$$T$$$ — the number of test cases. ($$$1 \le T \le 1000$$$)

The next $$$T$$$ lines each contain three integers $$$X, Y, N$$$. ($$$0 \le X, Y \le 10^9$$$, $$$2 \le N \le 10^6$$$) — the number of Type-Alpha BLUEs, the number of Type-Omega BLUEs, and the number of Anomaly Regulation Centers (ARCs).

Output

For each test case, output a single integer — the minimum possible difference between the maximum energy assigned to any ARC and the minimum energy assigned to any ARC.

Example
Input
5
2 2 3
1 4 3
3 2 3
0 5 3
3 0 3
Output
0
2
1
2
0
Note

In the first case, the distribution can be as follows:

  • The first ARC takes $$$2$$$ Type-Alpha BLUEs.
  • The second and third ARCs each take $$$1$$$ Type-Omega BLUE.
  • They all spent two energy units, so the difference is $$$0$$$.

In the second case, the distribution can be as follows:

  • The first ARC takes $$$1$$$ Type-Alpha BLUE and $$$1$$$ Type-Omega BLUE.
  • The second takes $$$2$$$ Type-Omega BLUEs.
  • The third takes $$$1$$$ Type-Omega BLUE.
  • The difference is $$$3$$$ (the first ARC) $$$- 1$$$ (the third ARC) $$$= 2$$$. It can be shown that this is the optimal assignment.