你正在观看 Alice 和 Bob 玩一个游戏。

这个游戏在一个长度为 $n$ 的数组上进行。Alice 和 Bob 轮流行动，Alice 先手。

在每一轮中，当前玩家可以选择数组中的两个不同数字 $a_i$ 和 $a_j$，然后改变它们的值。假设改变后的值为 $a_i'$ 和 $a_j'$，则该操作合法当且仅当 $a_i + a_j = a_i' + a_j'$ 且 $|a_i' - a_j'| < |a_i - a_j|$。无法进行合法操作的玩家输掉游戏。

在观看了几场比赛后，你决定帮助 Alice，因为 Alice 在面对一堆数字时总是感到不知所措，在天才 Bob 面前总是无法思考。

在每场游戏开始前，你将帮助 Alice 移除若干个数字（可以是 0 个）以减轻她的负担，并且你总是恰好留下三个数字。为了给 Alice 更大的获胜机会，你总是会给 Alice 留下一个必胜态，即必须存在某种操作策略，使得无论 Bob 如何行动，Alice 都能获胜。

现在的问题是，有多少种移除数字的方法。

如果存在一个整数 $i$ ($1 \le i \le n$)，使得在一种移除方式中 $a_i$ 没有被移除，而在另一种移除方式中 $a_i$ 被移除了，则这两种移除方式被认为是不同的。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($3 \le n \le 5 \times 10^5$)，表示初始数字的个数。

第二行包含 $n$ 个整数 $a_1, a_2, a_3, \dots, a_n$ ($0 \le a_i \le 10^{18}$)，表示原始的 $n$ 个数字。

保证 $\sum n \le 3 \times 10^6$。

输出格式

对于每个测试用例，输出一行一个整数，表示满足条件的移除数字的不同方法数。

样例

输入 1

3
4
2 0 2 3
3
2 2 3
3
0 2 3

输出 1

3
0
1

说明

在第一个测试用例中，只有移除 $a_2$ 会留下一个必败态。