题目描述

小远和小涛从下界挖来了 \(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