AT_KeioPC2025_a I Love MST Problem

有一个包含 $N$ 个顶点、$0$ 条边的图，每个顶点编号为 $1$ 到 $N$。你需要对 $k = 1, 2, \dots, N-1$ 执行如下操作： - 选择 $2$ 个顶点 $u, v$，在它们之间连接一条边。该操作的代价为 $((u + v) \times k) \bmod N$。 在 $N-1$ 次操作结束后，要求图是连通的。 请你求出 $N-1$ 次操作的总代价可能的最小值。 给定 $T$ 组测试数据，请分别输出对应答案。

输入从标准输入读入，格式如下： > $T$ > $\mathrm{case}_1$ > $\vdots$ > $\mathrm{case}_T$ 每组测试数据为： > $N$

请输出 $T$ 行，第 $i$ 行输出第 $i$ 组数据的答案。

### 样例解释 1 对于第 $1$ 个测试用例，可以如下操作使总代价为 $1$： - 当 $k = 1$ 时，选择 $u = 1, v = 4$，代价为 $((1 + 4) \times 1) \bmod 4 = 1$。 - 当 $k = 2$ 时，选择 $u = 2, v = 4$，代价为 $((2 + 4) \times 2) \bmod 4 = 0$。 - 当 $k = 3$ 时，选择 $u = 1, v = 3$，代价为 $((1 + 3) \times 3) \bmod 4 = 0$。 经过这些操作，最终图是连通的，并且总代价无法比 $1$ 更小，因此答案是 $1$。 ### 数据范围 - $1 \le T \le 100$ - $2 \le N \le 10^9$ - 输入均为整数。 由 ChatGPT 5 翻译