题目描述

联邦安全局截获了一起正在进行的黑客攻击：一个携带核心机密的数据包，正沿着一条线性的光纤隧道被秘密传输。

这条光纤隧道的总长度为 $L$，可将其视为一条从坐标 $0$（左端）到坐标 $L$（右端）的线段。情报显示，该数据包在光纤内的移动速度为恒定值 $V$，且已经传输了整整 $T$ 秒，即目前在光纤内推进了 $V \times T$ 的距离。

黑客的入侵源头尚不明确，因此数据包当前的位置存在两种可能：

1. 情况 A（左端入侵）：数据包位于坐标 $P_A = V \times T$ 处。
2. 情况 B（右端入侵）：数据包位于坐标 $P_B = L - V \times T$ 处。

你需要在光纤上选择一个整数坐标 $P$（$0 \le P \le L$）部署拦截程序。

为了使拦截方案尽可能稳妥，你需要衡量每一个坐标 $P$ 的偏差——即 $P$ 到 $P_A$ 的距离与 $P$ 到 $P_B$ 的距离中的较大者。

现在，请寻找一个最优的整数坐标 $P$，使得这个偏差值最小，并输出该最小值。

输入格式

第一行包含一个整数 $C$，表示测试用例的数量。

接下来的 $C$ 行，每行包含三个整数 $L, V, T$，分别表示光纤隧道的总长度、数据包的移动速度，以及已经传输的时间。

输出格式

对于每个测试用例，输出一行一个整数，表示最小偏差值。

3
100 2 10
51 5 2
200 10 10

30
16
0

提示

【样例说明】

对于第一组数据 $L = 100, V = 2, T = 10$：数据包推进了 $20$。它可能在情况 A（坐标 $20$）处，也可能在情况 B（坐标 $80$）处。选择整数坐标 $P = 50$，无论在哪边，距离都是 $30$。

对于第二组数据 $L = 51, V = 5, T = 2$：数据包推进了 $10$。它可能在情况 A（坐标 $10$）处，也可能在情况 B（坐标 $41$）处。最佳的整数坐标可以选择 $P = 25$：到 A 的距离是 $15$，到 B 的距离是 $16$，较大值为 $16$。或者选择 $P = 26$：到 A 的距离是 $16$，到 B 的距离是 $15$，较大值同样是 $16$。因此最小的最坏情况距离为 $16$。

对于第三组数据 $L = 200, V = 10, T = 10$：数据包推进了 $100$。无论从哪边开始，它现在都刚好在中心坐标 $100$ 处。直接将程序部署在 $P = 100$ 处，最大距离为 $0$。

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \le C \le 100$，$1 \le L, V, T \le 1000$。

对于所有评测用例，$1 \le C \le 10^5$，$1 \le L, V, T \le 10^{12}$，且保证 $V \times T \le L$。