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 翻译