Problem Description

The Federal Security Bureau has intercepted an ongoing hacking attack: a data packet carrying core secrets is being secretly transmitted along a linear fiber tunnel.

The total length of the fiber tunnel is $L$. You can treat it as a line segment from coordinate $0$ (left end) to coordinate $L$ (right end). Intelligence shows that the packet moves inside the fiber at a constant speed $V$, and it has been transmitted for exactly $T$ seconds. That is, it has moved a distance of $V \times T$ inside the fiber.

The source of the intrusion is still unclear, so the current position of the packet has two possibilities:

1. Case A (intrusion from the left end): the packet is at coordinate $P_A = V \times T$.
2. Case B (intrusion from the right end): the packet is at coordinate $P_B = L - V \times T$.

You need to choose an integer coordinate $P$ ($0 \le P \le L$) on the fiber to deploy an interception program.

To make the plan as reliable as possible, you need to measure the deviation at each coordinate $P$: the larger one of the distance from $P$ to $P_A$ and the distance from $P$ to $P_B$.

Now, find the best integer coordinate $P$ that minimizes this deviation, and output the minimum value.

Input Format

The first line contains an integer $C$, the number of test cases.

The next $C$ lines each contain three integers $L, V, T$, representing the total length of the fiber tunnel, the packet's moving speed, and the time it has been transmitted.

Output Format

For each test case, output one integer per line, representing the minimum deviation value.

3
100 2 10
51 5 2
200 10 10

30
16
0

Hint

Sample Explanation

For the first test case, $L = 100, V = 2, T = 10$: the packet has moved $20$. It may be in Case A (coordinate $20$) or in Case B (coordinate $80$). Choose the integer coordinate $P = 50$. No matter which side it is on, the distance is $30$.

For the second test case, $L = 51, V = 5, T = 2$: the packet has moved $10$. It may be in Case A (coordinate $10$) or in Case B (coordinate $41$). The best integer coordinate can be $P = 25$: the distance to A is $15$, and the distance to B is $16$, so the larger one is $16$. Or choose $P = 26$: the distance to A is $16$, and the distance to B is $15$, and the larger one is also $16$. Therefore, the minimum worst-case distance is $16$.

For the third test case, $L = 200, V = 10, T = 10$: the packet has moved $100$. No matter which side it started from, it is now exactly at the center coordinate $100$. Deploy the program directly at $P = 100$, and the maximum distance is $0$.

Constraints and Notes

For $30\%$ of the test cases, $1 \le C \le 100$, $1 \le L, V, T \le 1000$.

For all test cases, $1 \le C \le 10^5$, $1 \le L, V, T \le 10^{12}$, and it is guaranteed that $V \times T \le L$. In particular, the testdata additionally satisfies $V \times T < L / 2$, but this is not stated in the original problem statement.

Translated by ChatGPT 5