题目描述

小远和小涛从下界挖来了 $998244353^{1145141919810}$ 颗萤石，由于实在是太多了，他们决定拿这些萤石来玩个游戏。

小远和小涛决定玩 $t$ 次游戏，每次游戏给定长度为 $n$ 的数组 $a$。

定义 $f(i,j,k)=a_i \cdot k^{a_i+a_j}+a_j$.

每次游戏，小远和小涛将随机选择两个正整数 $(i,j) (1 \le i,j \le n)$，取$l=\min(i,j),r=\max(i,j),k=\max_{x=l}^r a_x$。小远和小涛会将 $f(i,j,k)$ 颗萤石堆成一堆，轮流从堆中取萤石，每次取出 $1$ 到 $k$ 之间任意颗，取到最后一颗萤石的人获胜，小远先手，两人都采取最佳策略。

小远想知道，有多少对 $(i,j)$ 可以使他获胜。

数据范围：$1\le t \le 10,1 \le n \le 10^5,2 \le a_i \le 10^9$。

样例解释：

例如，当选中的 $(i,j)$ 为 $(1,5)$ 时，小远和小涛将用$f(3,5,7)=17294408$ 颗萤石来进行游戏，在双方都采取最佳策略的情况下，小远必败。

输入格式

第一行一个正整数 $t$ 表示用例组数，接下来每组用例第一行一个正整数 $n$，第二行 $n$ 个正整数表示数组 $a$。

输出格式

一个整数表示可以使小远获胜的 $(i,j)$ 对数。

输入输出样例

1
5
3 2 7 6 5

21