题目描述

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

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

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

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

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

输入格式

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

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

输出格式

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

3
4
6
100

4
12
4900