#include<stdio.h>
#include<memory.h>
#include<algorithm>
#include<queue>
using namespace std;
#define N 1020
queue < pair< int, int> > ans2;
int main(void)
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t, n, tempn, p, ans = 0;
int man[N];
scanf("%d", &t);
for(int i = 0; i<t; i++){
scanf("%d", &n);
memset(man, 0, sizeof(int) * N);
ans = 0;
for(int j = 0; j<n; j++){
scanf("%d", &man[j]);
}
sort(man, man + n);
tempn = n;
p = n-1;
while(tempn > 0){
if(tempn >= 4){
if(man[0] + man[1] + man[p] + man[1] > man[p] + man[0] + man[p-1] + man[0]){
ans += man[p] + man[0] + man[p-1] + man[0];
ans2.push(make_pair(man[0], man[p]));
ans2.push(make_pair(man[0], -1));
ans2.push(make_pair(man[0], man[p-1]));
ans2.push(make_pair(man[0], -1));
}
else{
ans += man[0] + man[1] + man[p] + man[1];
ans2.push(make_pair(man[0], man[1]));
ans2.push(make_pair(man[0], -1));
ans2.push(make_pair(man[p-1], man[p]));
ans2.push(make_pair(man[1], -1));
}
tempn -= 2;
p -= 2;
}
else{
if(tempn == 3){
ans += man[0] + man[p] + man[1];
ans2.push(make_pair(man[0], man[p]));
ans2.push(make_pair(man[0], -1));
ans2.push(make_pair(man[0], man[1]));
tempn = 0;
}
else if(tempn == 2){
ans += man[1];
ans2.push(make_pair(man[0], man[1]));
tempn = 0;
}
else if(tempn == 1){
ans += man[0];
ans2.push(make_pair(man[0], -1));
tempn = 0;
}
}
}
printf("%d\n", ans);
while(!ans2.empty()){
pair <int, int> temp;
temp = ans2.front();
ans2.pop();
printf("%d", temp.first);
if(temp.second != -1)printf(" %d", temp.second);
printf("\n");
}
if(i != t-1)printf("\n");
}
}
10545698 10037 Bridge Accepted C++ 0.012 2012-08-31 04:45:34