Description

勇者闯终于直面魔王肖了，面对魔王肖的爪牙军团时，勇者闯用了一个大魔法阵将魔王肖的爪牙军队尽数秒杀。可惜，魔王肖过于强大，勇者闯被其一记必杀技打的血量见底。魔王肖再次释放技能，当这记攻击距离勇者闯还有0.01厘米的时候，突然！时间暂停，神明出现！

神明对勇者闯说：“我可以让你重回巅峰时刻，但是这是一个阵法，需要你完成以下的问题，才可以启动它。要不要试一试。”

勇者回答：“废话，一定要启动它，不然我不就挂了！问题是啥？”

神明给出了启动阵法的问题：

这里有n条木棒，木棒的长度分别为1,2,3...n，问，任意选取三根不同的木棍，最多能构成多少种三角形。

注意：当两个三角形存在一条或多条边长度不相同时，我们认为这两个三角形是不同的。

你能帮勇者闯回答这个问题，从而重回巅峰，与魔王肖进行决战吗？

Input Format

第一行输入一个整数T表示测试样例数(1≤T≤10^6)

对于每组测试样例：

输入一行，该行输入一个正整数n(3≤n≤10^6)，表示木棒的数量。

注意：该题数据量较大，请使用较快的读入和输出方式。如：scanf和printf。

Output Format

对于每组测试样例：

输出一行，该行包含一个正整数，表示能组成的三角形的种类数。

2
3
5

0
3

Hint

样例说明：

对于测试样例一：

当木棒的数量为三的时候，木棒的长度分别为：1，2，3。此时没有办法组成任何三角形。

对于测试样例二：

当木棒的数量为五的时候，木棒的长度分别为：1，2，3，4，5。此时可以组成三种三角形：(2，4，5)，(2，3，4)和(3，4，5)。

Source

1816 Online Judge 10.100.0.232