Even the World Tree must bow to the cycle of life. Everything born will die.
Archimonde has hurt it once, Sylvanas burnt it again.
Now the World Tree is slowly recovering.
The World Tree is burnt apart into n parts. Now it tries to rebuild itself.
Each part of the World Tree has an attribute pi, and all pi (1≤i≤n) forms a permutation of 1,2,3...n.
For all 1≤i<j≤n, if the World Tree wants to grow an edge connecting part ii and part j directly, it needs to spend ∣i−j∣∗∣pi−pj∣ energy. ∣x∣ means the absolute value of x.
The World Tree is very smart, so it will grow some edges such that all its n parts become connected (in other words, you can go from any part to any other part using only the edges that have been grown), spending the minimum energy.
Please calculate the minimum energy the World Tree needs to spend.
The input consists of multiple test cases.
The first line contains an integer T (1≤T≤5) denoting the number of test cases.
For each test case, the first line contains a single integer n(1≤n≤50000).
The second line contains n integers pi (1≤pi≤n), it's guaranteed that all pi forms a permutation.
2
5
4 3 5 1 2
10
4 7 3 8 6 1 9 10 5 27
24