Description

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

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

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

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

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

Format

Input

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

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

Output

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

Samples

3
4
6
100

4
12
4900