题目描述

对于一个长度为 $L$ （$L$ 为奇数） 的数组 $a$，定义它的中位数 $median(a)$ 为 $a$ 中第 $\frac{L+1}{2}$ 大的数。

现在给你一个长度为 $n$ 的排列，对于每对满足 $1 \le i \le j \le n$ 且 $j - i \equiv 0 \pmod 2$ 的 $(i,j)$，你需要计算 $i \times j \times median(p[i \dots j])$。

输出所有值的总和。

输入格式

第一行输入一个整数 $T$ $(1 \le T \le 20)$，表示测试的总数。

对于每个测试用例：

• 第一行输入一个整数 $n$ $(1 \le n \le 2000)$。
• 接下来一行 $n$ 个整数，表示 $1$ 到 $n$ 的排列。

输出格式

对于每个测试用例，输出一个整数，表示答案。

样例

输入

2
3
1 3 2
5
2 3 1 5 4

输出

37
308