Thiết lập đường truyền

Một hệ thống viễn thông bao gồm $n$ trạm phát sóng độc lập được đánh số từ $1$ đến $n$. Ban đầu, giữa các trạm chưa có bất kỳ kênh truyền thông nào. Mỗi trạm $i$ có một mức nhiễu tín hiệu ban đầu là $g_i$.

Người quản trị có thể thực hiện thao tác sau đây với số lần tùy ý: chọn hai trạm $i$ và $j$ bất kỳ ($i ≠ j$) và cung cấp cho hai trạm này $\max(g_i, g_j)$ đơn vị năng lượng để chia sẻ. Khi đó, mức nhiễu tín hiệu của cả hai trạm đều giảm đi $\min(g_i, g_j)$, đồng thời giữa hai trạm sẽ hình thành một kênh truyền thông trực tiếp nếu trước đó chúng chưa kết nối với nhau.

Người quản trị muốn tất cả các trạm trong hệ thống đều có thể liên lạc được với nhau, tức là từ một trạm bất kỳ đều có thể đi theo một chuỗi các kênh truyền thông trực tiếp hoặc gián tiếp để đến mọi trạm khác. Vì muốn tiết kiệm tối đa tài nguyên, hãy tính tổng số đơn vị năng lượng tối thiểu cần tiêu hao để toàn bộ hệ thống trở nên liên thông.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $t$ ($1 ≤ t ≤ 10^4$), biểu thị số lượng nhóm thử nghiệm. Các dòng tiếp theo mô tả từng nhóm thử nghiệm.

Dòng đầu tiên của mỗi nhóm thử nghiệm chứa số nguyên $n$ ($2 ≤ n ≤ 2 · 10^5$), biểu thị số lượng trạm phát sóng. Tổng của $n$ qua tất cả các nhóm thử nghiệm không vượt quá $2 · 10^5$ ($\sum n ≤ 2 · 10^5$).

Dòng thứ hai của mỗi nhóm thử nghiệm chứa $n$ số nguyên $g_1, g_2, ..., g_n$ ($1 ≤ g_i ≤ 10^9$), trong đó $g_i$ là mức nhiễu tín hiệu ban đầu của trạm phát sóng thứ $i$.

Kết quả

Với mỗi nhóm thử nghiệm, in ra một số nguyên duy nhất là tổng năng lượng tối thiểu cần tiêu hao để kết nối toàn bộ hệ thống trạm phát sóng.

Chấm điểm

Subtask 1 (30 points). $\sum n ≤ 2000$

Subtask 2 (70 points). $1 ≤ t ≤ 10^4$; $2 ≤ n ≤ 2 · 10^5$; $\sum n ≤ 2 · 10^5$

Ví dụ

Input

1
3
4 7 2

Output

9

Ghi chú

Trong ví dụ mẫu, có $n = 3$ trạm với mức nhiễu ban đầu lần lượt là $[4, 7, 2]$:

• Người quản trị chọn trạm 1 (mức nhiễu 4) và trạm 2 (mức nhiễu 7) với chi phí $\max(4, 7) = 7$ đơn vị năng lượng. Mức nhiễu của cả hai trạm giảm đi $\min(4, 7) = 4$, đưa mức nhiễu của hệ thống về $[0, 3, 2]$. Kênh truyền thông trực tiếp giữa trạm 1 và trạm 2 được thiết lập.
• Tiếp theo, người quản trị chọn trạm 1 (mức nhiễu 0) và trạm 3 (mức nhiễu 2) với chi phí $\max(0, 2) = 2$ đơn vị năng lượng. Mức nhiễu của cả hai trạm giảm đi $\min(0, 2) = 0$, đưa mức nhiễu của hệ thống về $[0, 3, 2]$. Kênh truyền thông trực tiếp giữa trạm 1 và trạm 3 được thiết lập.

Sau hai thao tác, các kênh truyền thông $(1, 2)$ và $(1, 3)$ giúp toàn bộ ba trạm kết nối liên thông với nhau. Tổng năng lượng tiêu hao là $7 + 2 = 9$, đây là chi phí tối thiểu có thể đạt được.