#include <iostream.h>

/*-------------  qksort  below------------*/
int Partition(int *L, int low, int high)
{
     
     int pivot =  L[low];   
     while(low<high)
     {
          while(low<high&&L[high]>=pivot)
                --high;
          L[low] = L[high];
          while(low<high&&L[low]<=pivot)
                ++low;
          L[high] = L[low];               
     } //while
     L[low] = pivot;
     return low;
}// Partition

void qksort(int *L, int start, int end)   
{
         int pivotloc;
         if(start<end)
         {
               pivotloc = Partition(L, start, end);
               qksort(L, start, pivotloc-1);
               qksort(L, pivotloc+1, end);             
         }
         return; 
}
/*---------- qksort above---------*/


int test, n, t[1001]={0};


int solve(int n)             // 返回 n 個人渡河所需時間 
{
      int total=0;
     
      while(n>=4)  
      {
           if(2*t[2]>=t[1]+t[n-1]) 
                 total += 2*t[1]+t[n-1]+t[n];                
                           
           else if(2*t[2]<t[1]+t[n-1])  
                 total += 2*t[2]+t[1]+t[n]; 
           n = n-2; 
      }
      if(n<=2)  total += t[n]; 
      else if(n==3)  total += t[2] + t[1] + t[3];
      return total; 
      
}

int main()
{
     int i, j, tot;
     cin>>test;
     for(i=1; i<=test; i++)
     {
          cin>>n;
          for(j=1; j<=n; j++) 
              cin>>t[j];
         
                  
         qksort(t, 1, n);     // 也可直接調用<stdlib.h> void qsort(void *base, size_t n, size_t n, int(*cmp)(const void*, const void *))
         
         tot = solve(n);
         cout<<tot<<endl;
     }//for
     return 0;
}