#include <iostream>

using namespace std;

#define MAX_N 110

int N;
unsigned int arr[MAX_N];
unsigned int stack[MAX_N];
unsigned int top = -1;

void swap(unsigned int a[], int left, int right){
    int temp = a[left];
    a[left] = a[right];
    a[right]  =temp;
}

void quickSort(unsigned int a[], int left, int right){
    int pivot, i, j;
    if(left<right){
        i = left, j = right +1, pivot = a[left];
        do
        {
            do
            i++;
            while(a[i] < pivot);
            do
            j--;
            while(a[j] > pivot);
            if(i<j) swap(a, i, j);
        }while(i<j);
        swap(a, left, j);
        quickSort(a, left, j-1);
        quickSort(a, j+1, right);
    }
}

void init(){
    top = -1;
    N=0;
    for(int i=0; i<MAX_N; i++)
        arr[i] = 0;
}

void calculate(){
    //1. arr 배열을 quickSort합니다.
    //2. N길이가 2가 된다면 stack에 넣고 종료합니다.
    //3. arr 배열의 1번과 2번을 합쳐서 stack에 넣습니다. 
    //4. arr 배열을 왼쪽으로 두칸 이동합니다. 마지막에는 stack의 마지막값을 넣습니다.

    //1. 
    quickSort(arr, 0, N-1);

    //2.
    if(N==2){
        unsigned int sum=0;
        sum = arr[0] + arr[1];
        stack[++top] = sum;
        return;
    }

    //3. 
    unsigned int sum=0;
    sum = arr[0] + arr[1];
    stack[++top] = sum;

    //4. 
    for(int i=2; i<N; i++)  arr[i-2] = arr[i];
    arr[N-2] = sum;
    N -= 1;

    calculate();
}

int main(int argc, char** argv)
{
    int test_case;
    int T;

    cin >> T;
    for(test_case = 0; test_case < T; test_case++)
    {
        init();
        cin>>N;
        for(int i=0; i<N; i++)
            cin>>arr[i];

        calculate();

        //stack에 있는 모든 값을 더해보자.
        unsigned int s = 0;
        for(int i=0; i<=top; i++) s += stack[i];
        cout<<s<<endl;

    }

    return 0;
}