/*입력받은 문자열을 2개씩 분리한 뒤 정렬하여 합친 결과를 반환하여라.*/
#include <iostream>
#include <string>
using namespace std;
#define MAX_SIZE 1000 //문자열의 최대사이즈는 1000
//void quickSort(string *arr, int left, int right, int size);
void sort(string *arr, int size);
int main(){
int count; //테스트케이스 수
int index = 0; //while문을 돌릴 변수
int size = 0; //문자열의 절반 길이를 넣는 변수(2개씩 묶이니까)
string str;
string result; //정렬이 완료된 문자열을 넣는 변수
string *super; //테스트케이스 개수만큼 나열될 문자 배열
string *arr; //자른 문자열을 저장할 변수
cin>>count;
super = new string[count];
for(int i=0;i<count;i++){
cin>>str;
size = (str.length())/2;
arr = new string[MAX_SIZE];
while(!str.empty()){ //2개씩 자르기
arr[index] = str.substr(0, 2);
//cout<<arr[index]<<" / "<<str<<endl;
str.erase(0,2);
index++;
}
//quickSort(arr, 0, size-1, size);
sort(arr, size-1);
for(int j=0;j<size;j++){
result.append(arr[j]);
}
super[i] = result; //합쳐진 문자열을 super에 대입
//기존에 쓰이던 변수들 초기화
index = 0;
result.erase();
}
for(int i=0;i<count;i++){
cout<<super[i]<<endl;
}
delete []super;
delete []arr;
return 0;
}
/*void quickSort(string *arr, int left, int right, int size){
if(left<right){
int i = left;
int j = right+1;
string pivot = arr[left];
do{
do {
i++;
cout<<"i : "<<i<<" ";
if(i>j) break;
}while((pivot.compare(arr[i])>=0)&&i<=right);
cout<<endl;
do {
j--;
cout<<"j : "<<j<<" ";
if(j<i) break;
}while((pivot.compare(arr[j])<0)&&j>=left);
cout<<endl;
if(i<j){arr[i].swap(arr[j]);}
}while(i<j);
arr[left].swap(arr[j]);
cout<<"swap : "<<left<<"<->"<<j<<endl;
for(int i=0;i<size;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
cout<<"j-1 "<<j-1<<" j+1 "<<j+1<<endl;
quickSort(arr, left, j-1, size);
quickSort(arr, j+1, right, size);
}
}*/
void sort(string *arr, int size){
int *stack = new int[2*size+2];
int top = -1;
int start, end, left, right;
string pivot;
//stack push
stack[++top] = size;
stack[++top] = 0;
while(top!=-1){ //stack이 비어있지 않을 때
//stack pop(먼저 들어간게 나중에)
start = stack[top--];
//cout<<"start : "<<start<<endl;
//cout<<"start top : "<<top<<endl;
end = stack[top--];
//cout<<"end : "<<end<<endl;
//cout<<"end top : "<<top<<endl;
if(start<end){ //정렬할만한 크기가 될 때
left = start;
right = end+1;
pivot = arr[left];
do {
do {left++;} while((left<=end)&&(pivot.compare(arr[left])>=0)); //pivot보다 크면 멈춤
do {right--;} while((right>=start)&&(pivot.compare(arr[right])<0)); //pivot보다 작으면 멈춤
if(left<right){ //교차하지 않았을 때
arr[left].swap(arr[right]);
}
}while(left<right);
arr[start].swap(arr[right]);
/*for(int i=0;i<size+1;i++){
cout<<arr[i]<<" ";
}
cout<<endl;*/
//앞으로 정렬해야 할 범위들을 stack에 저장
stack[++top] = end;
stack[++top] = right+1;
stack[++top] = right-1;
stack[++top] = start;
}
}
delete []stack;
}