Cho \(N\) sợi dây với độ dài khác nhau được lưu trong mảng \(A\). Nhiệm vụ của bạn là nối \(N\) sợi dây thành một sợi sao cho tổng chi phí nối dây là nhỏ nhất. Biết chi phí nối sợi dây thứ \(i\) và sợi dây thứ \(j\) là tổng độ dài hai sợi dây \(A_i\) và \(A_j\).

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(T\) (\(1 \leq T \leq 100\)).
• Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test gồm hai dòng:
  • Dòng thứ nhất đưa vào số lượng sợi dây \(N\) (\(1 \leq N \leq 10^6\));
  • Dòng tiếp theo đưa vào \(N\) số \(A_i\) (\(1 \leq i \leq N, 0 \leq A_i \leq 10^6\)) là độ dài của các sợi dây;
• Các số được viết cách nhau một vài khoảng trống.

Output

• Đưa ra kết quả mỗi test theo từng dòng.

Example

2
4
4 3 2 6
5
4 2 7 6 9

29
62