この問題にはいくつかの部分点が設定されています。
問題
正整数$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型に収まらない場合があります。