即使是世界之树也必须向生命循环低头。万物终有一死。 阿克蒙德曾伤害过它，希尔瓦娜斯又再次将其焚毁。 现在，世界之树正在缓慢恢复。

世界之树被烧成了 $n$ 个部分。现在它试图重建自身。 世界之树的每个部分都有一个属性 $p_i$，且所有 $p_i$ ($1 \le i \le n$) 构成了一个 $1, 2, 3, \dots, n$ 的排列。 对于所有 $1 \le i < j \le n$，如果世界之树想要生长一条直接连接部分 $i$ 和部分 $j$ 的边，它需要消耗 $|i - j| \cdot |p_i - p_j|$ 的能量。$|x|$ 表示 $x$ 的绝对值。

世界之树非常聪明，它会生长一些边，使得其 $n$ 个部分全部连通（换句话说，你只需使用已生长的边，就能从任意一个部分到达其他任何部分），并消耗最少的能量。 请计算世界之树需要消耗的最小能量。

输入格式

输入包含多个测试用例。 第一行包含一个整数 $T$ ($1 \le T \le 5$)，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 50000$)。 第二行包含 $n$ 个整数 $p_i$ ($1 \le p_i \le n$)，保证所有 $p_i$ 构成一个排列。

输出格式

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

样例

样例输入 1

2
5
4 3 5 1 2
10
4 7 3 8 6 1 9 10 5 2

样例输出 1

7
24