L. 三人成角

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在 CCPC 省赛的颁奖晚宴上，场地中央摆放着一张巨大的圆形主桌。工作人员沿着圆桌边缘等距离地放置了 $N$ 把椅子。

晚宴开始后，有 3 名参赛选手提前进入会场，并从这 $N$ 把椅子中任意选择了 3 把不同的椅子坐下。坐定后，其中一个人突然问道：

“我们三个人的位置在圆周上恰好构成一个三角形。在所有可能的选座方案中，有多少种方案对应的三角形是直角三角形？”

现在，请你编写一个程序回答这个问题。

注意：一种选座方案只有最终被选中的 3 把椅子决定，不区分三名选手分别坐在哪个位置。换句话说，这是一个组合问题，而不是排列问题。

第一行包含一个整数 $T(1 \le T \le 10^5)$ ，表示测试数据的组数。

接下来 $T$ 行，每行包含一个整数 $N（3 \le N \le 10^9）$ ，表示圆桌周围椅子的总数量。

对于每组测试数据，输出一行一个整数，表示能构成直角三角形的方案数。

4
12
4900