AT_KeioPC2025_a I Love MST Problem

頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点 $ 0 $ 辺のグラフがあります。あなたは $ k = 1,2,\dots , N-1 $ に対して以下の操作を行います。 - $ 2 $ つの頂点 $ u, v $ を選び、その間に辺を張る。この操作のコストは $ (u + v) \times k $ を $ N $ で割ったあまりとする。 ただし、 $ N-1 $ 回の操作が終了したときグラフが連結になっている必要があります。 $ N-1 $ 回の操作のコストの総和としてありうる最小値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $

$ T $ 行出力せよ。 $ i $ 行目には $ \mathrm{case}_i $ の答えを出力せよ。

### Sample Explanation 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 $ 終了時にグラフが連結になるように操作する方法であって、コストの総和は $ 0 $ 以下のものはないため、答えは $ 1 $ です。 ### Constraints - $ 1 \le T \le 100 $ - $ 2 \le N \le 10^9 $ - 入力はすべて整数