题目描述

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

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

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

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

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

输入格式

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

输出格式

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

1
5
3 2 7 6 5

21

解释 #1

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

数据范围

$1\leq t\leq 10,1\leq n\leq 10^5,2\leq a_i\leq 10^9$。