/*************************************************************************
* Copyright (C) 2008 by Moustafa Mahmoud (cmpsamurai) *
* moustafa@cmpsamurai.com *
*************************************************************************/
/*C++ "10037 - Bridge" */
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <iterator>
#include <sstream>
using namespace std;
void cross(deque<int> runners)
{
deque<int> first,second;
first=runners;
int time=0;
stringstream output;
int temp=-1,last1,last2;
while(second.size()<runners.size())
{
sort(first.begin(),first.end());
sort(second.begin(),second.end());
if(first.size()==1)
{
output<<first.front()<<endl;
time+=first.front();
second.push_front(first.front());
first.pop_front();
}
else if(first.size()==2)
{
output<<first[0]<<" "<<first[1]<<endl;
time+=first[1];
second.push_back(first.front());
first.pop_front();
second.push_back(first.front());
first.pop_front();
}
else if(first.size()==3)
{
output<<first[0]<<" "<<first[2]<<endl;
time+=first[2];
second.push_back(first[0]);
second.push_front(first[2]);
first.pop_front();
first.pop_back();
sort(second.begin(),second.end());
output<<second[0]<<endl;
time+=second[0];
output<<second[0]<<" "<<first[0]<<endl;
time+=first[0];
second.push_back(first[0]);
}
else
{
bool test1=(first[1]+first[0]+first[first.size()-2]+first[1])<(first[0]+first[0]+first[first.size()-1]+first[first.size()-2]);
if(test1)
{
//first 2
output<<first[0]<<" "<<first[1]<<endl;
time+=first[1];
second.push_back(first[0]);
second.push_back(first[1]);
first.pop_front();
first.pop_front();
sort(second.begin(),second.end());
first.push_front(second[0]);
output<<second[0]<<endl;
time+=second[0];
second.pop_front();
//last 2
output<<first[first.size()-2]<<" "<<first[first.size()-1]<<endl;
time+=first[first.size()-1];
second.push_back(first[first.size()-2]);
second.push_back(first[first.size()-1]);
first.pop_back();
first.pop_back();
first.push_front(second.front());
time+=first.front();
output<<first.front()<<endl;
second.pop_front();
}
else
{
//first 2
output<<first[0]<<" "<<first[first.size()-1]<<endl;
time+=first[first.size()-1];
second.push_back(first[0]);
second.push_back(first[first.size()-1]);
first.pop_front();
first.pop_back();
sort(second.begin(),second.end());
first.push_front(second[0]);
output<<second[0]<<endl;
time+=second[0];
second.pop_front();
//last 2
output<<first[0]<<" "<<first[first.size()-1]<<endl;
time+=first[first.size()-1];
second.push_back(first[0]);
second.push_back(first[first.size()-1]);
first.pop_back();
first.pop_front();
sort(second.begin(),second.end());
first.push_front(second.front());
time+=first.front();
output<<first.front()<<endl;
second.pop_front();
}
}
}
cout<<time<<endl;
cout<<output.str();
}
int main() {
int num_cases,n,temp;
string line;
cin>>num_cases;
getline(cin,line);
for(int i=0;i<num_cases;i++)
{
getline(cin,line);
cin>>n;
cin.ignore();
deque<int> speeds;
for(int j=0;j<n;j++)
{
cin>>temp;
cin.ignore();
speeds.push_back(temp);
}
cross(speeds);
if(i<num_cases-1)
{
cout<<endl;
}
}
return 0;
}