003 - =N problems

この問題にはいくつかの部分点が設定されています。

問題

正整数$N$が与えられます。
正整数$a,b,c$の組であって、$a+b+c=N$であるものの個数を出力してください。
$Q$個のクエリについてこたえてください。

入力

入力は以下の形式で標準入力から与えられる。

$Q$
$N_1$
$N_2$
...
$N_Q$

1行目に整数$Q$が与えられる。 2行目から$Q$行にわたって整数$N$が与えられる。

出力

$i$個目のクエリに対する答えを$i$行目に出力してください。
出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq Q \leq 20$
• $3 \leq N \leq 10^9$
• 入力はすべて整数

部分点1(50点)の入出力ケースについて以下を満たす。

• $N \leq 100$

部分点2(50点)の入出力ケースについて以下を満たす。

• $N \leq 3000$

部分点3(50点)の入出力ケースについて以下を満たす。

• $N \leq 5×10^5$

入出力例

入力例1

5
3
4
8
13
100

出力例1

1
3
21
66
4851

1つ目のクエリについて、{a,b,c}={1,1,1}の組のみが条件を満たします。
2つ目のクエリについて、{a,b,c}={2,1,1},{1,2,1},{1,1,2}の3通りの場合で条件を満たします。

入力例2

2
1000000000
998244353

出力例2

499999998500000001
498245892650827776

答えはint型に収まらない場合があります。