algoH1

#include <iostream>
#include <time.h>
#include <decimal/decimal>
#include <bitset>
#include <algorithm>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#define For(a, b, c) for(int b=a; b<c; b++)
#define rFor(a, b, c) for(int b=a; b>c; b--)
//#include <vector>
using namespace std;
string a;
struct node{
    char val;
    node* Lch;
    node* Rch;

    node(char value, node * Lnode, node * Rnode){
        val = value;
        Lch = Lnode;
        Rch = Rnode;
    }
};

void build(node* curNode, int & curIndex){
    if(curIndex == -1)
        return;

    if(curNode->val > 'Z')
        return;

    if(curNode->Rch == NULL){
        curIndex--;
        curNode->Rch = new node(a[curIndex], NULL, NULL);
        build(curNode->Rch, curIndex);
    }

    if(curNode->Lch == NULL){
        curIndex--;
        curNode->Lch = new node(a[curIndex], NULL, NULL);
        build(curNode->Lch, curIndex);
    }

}

void print(node* head){
    queue<node*> qq;
    qq.push(head);
    int i = a.length();
    while(!qq.empty()){
        a[--i] = qq.front()->val;
        node* z = qq.front();
        qq.pop();
        if(z->Lch != NULL)
            qq.push(z->Lch);

        if(z->Rch != NULL)
            qq.push((z->Rch));
    }
}

int main()
{
    //algo homework

    clock_t end; clock_t start;

    int n;
    cin>>n;


for(int i=0; i<n; i++){
    cin>>a;

    //cout<<(a[a.length()-1]);
    node* head = new node(a[a.length()-1], NULL, NULL);

    int curIndex = a.length()-1;

    build(head, curIndex);

    print(head);

    cout<<a<<endl;
}

    return 0;
}