問題文

頂点に 1 から N の番号がついた N 頂点 0 辺のグラフがあります。あなたは k = 1,2,\dots , N-1 に対して以下の操作を行います。

• 2 つの頂点 u, v を選び、その間に辺を張る。この操作のコストは (u + v) \times k を N で割ったあまりとする。

ただし、N-1 回の操作が終了したときグラフが連結になっている必要があります。

N-1 回の操作のコストの総和としてありうる最小値を求めてください。

T 個のテストケースが与えられるので、それぞれについて解いてください。

制約

• 1 \le T \le 100
• 2 \le N \le 10^9
• 入力はすべて整数

入力例 1

3
4
56
789

出力例 1

1
0
130

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 です。