4486: 公交通勤

Nanarikom 正在通过 548 路公交通勤。

Nanarikom 喜欢在均匀随机的时间抵达公交站。规划上，548 路公交在始发站的发车间隔为固定的 $t$ 分钟，容易发现此时 Nanarikom 的期望等车时间为 E = \frac{t}{2}E=2t；但实际上，由于车况等因素的影响，548 路公交并非均匀地每 $t$ 分钟到达 Nanarikom 所在站点。记第一趟车在第 $0$ 分钟到达，则后续的 $n$ 趟车将分别在第 a_1, a_2, \dots, a_{n - 1}, nta1,a2,…,an−1,nt 分钟到达，且其后每 $n$ 趟车的到达时间以相同的偏移量和相同的周期（$nt$ 分钟）而循环。

Nanarikom 注意到，某些等车区间相较更长，而这就意味着有更大的概率落入更长的等车区间，因此，实际上，Nanarikom 的期望等车时间 E \geq \frac{t}{2}E≥2t，并且只在 a_i = itai=it 时取等。

现在，Nanarikom 可以进行修改道路规划的操作以改变 $a$ 序列。其中，每次操作可以在 $[1,n-1]$ 中选择 $i$，然后指定以下两种结果中的一种：

• 对于指定的 $i$，将 a_iai 修改为 \min(n \cdot t, a_i + 1)min(n⋅t,ai+1)；
• 对于指定的 $i$，将 a_iai 修改为 \max(0, a_i - 1)max(0,ai−1)。

为了方便通勤，Nanarikom 想知道，进行不多于 $m$ 次操作后，可以得到的最小期望等车时间是多少。为简化运算，你只需要告知 Nanarikom 将答案乘 $2nt$ 后的结果。

你需要回答 Nanarikom 的 $T$ 组询问。