1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 
 5 int a[1010];
 6 int n, t, i;
 7 int ans;
 8 
 9 int cmp(const void *a, const void *b){
10     return *(int *)a - *(int *)b;
11 }
12 
13 void solve(){
14     ans = 0;
15     while(n){
16         if(n == 1){
17             ans += a[1];
18             break;
19         }
20         else if(n == 2){
21             ans += a[2];
22             break;
23         }
24         else if(n == 3){
25             ans += a[1] + a[2] + a[3];
26             break;
27         }
28         else{
29             //人较多的情况下，判断是先把走得最慢的两个人送过去合算还是先把走得最快和最慢的人先送过去
30             if(2 * a[2] > a[1] + a[n - 1]){
31                 ans += (a[n - 1] + a[n] + 2 * a[1]);
32             }
33             else{
34                 ans += (a[1] + 2 * a[2] + a[n]);
35             }
36             n -= 2;
37         }
38     }
39     printf("%d\n", ans);
40 }
41 
42 int main(){
43     scanf("%d", &t);
44     while(t--){
45         scanf("%d" ,&n);
46         for(i = 1; i <= n; i++){
47             scanf("%d", &a[i]);
48         }
49         qsort(a + 1, n, sizeof(a[1]), cmp);
50         solve();
51     }
52     return 0;