Cho số nguyên dương \(n\) và dãy số nguyên \(a_1,a_2,…,a_n\), có thể thay đổi không quá một số trong dãy \(a\) để thu được dãy \(b\) sao cho:

\(S= (|a_1-b_1| + |a_2-b_2| +... + |a_k - b_k|) + (k × c_1 + k × c_2 +... + k × c_k)\) đạt giá trị nhỏ nhất.

Với \(c_k\) là số lượng giá trị phân biệt trong \({b_1,b_2,…,b_k }\)

Input

• Dòng đầu chứa số lượng testcase \(T\). Với mỗi testcase:

• Dòng đầu chứa số nguyên \(n\).

• Dòng tiếp theo chứa \(n\) số nguyên \(a_1,a_2,…,a_n\)

Output

Với mỗi testcase, ghi một số là giá trị \(S\) nhỏ nhất tìm được.

Sample Input

1
4
1 2 3 4
``
## Sample Output

22 ```

Hạn chế

• Có 50% số test với tổng \(n\) trong tất cả các testcase không quá 3000.

• Có 50% số test với tổng \(n\) trong tất cả các testcase không quá \(10^6,1≤a_i≤10^9\)