/* Christoph Schwirzer */
#include <cstdio>
#include <iostream>
#include <vector>
#include <cassert>
#include <cctype>
#include <queue>
using namespace std;
typedef vector<string> VS;
struct node
{
	node() {}
	node(char ch, int left, int right) : ch(ch), left(left), right(right) {}
	char ch;
	int left, right;
};

int main()
{
	int t;
	cin >> t;
	string tmp;
	getline(cin, tmp);
	while (t--)
	{
		string e;
		getline(cin, e);
		if (e.empty())
		{
			cout << endl;
			continue;
		}
		VS st;
		vector<node> v;
		vector<node> w;
		for (string::iterator it = e.begin(); it != e.end(); ++it)
		{
			if (isupper(*it))
			{
				assert(v.size() >= 2);
				w.push_back(v[v.size() - 1]);
				w.push_back(v[v.size() - 2]);
				v.pop_back();
				v.pop_back();
				v.push_back(node(*it, w.size() - 1, w.size() - 2));
			}
			else
				v.push_back(node(*it, -1, -1));
		}
		w.push_back(v[0]);
		queue<int> q;
		q.push(w.size() - 1);
		string s;
		while (!q.empty())
		{
			int act = q.front();
			q.pop();
			s += w[act].ch;
			if (w[act].left != -1)
			{
				q.push(w[act].left);
				q.push(w[act].right);
			}
		}
		reverse(s.begin(), s.end());
		cout << s << endl;
	}
	return 0;
}
