> #include "iostream"
> #include "string"
> #include "vector"
> #include "deque"
> 
> using namespace std;
> 
> struct node
> {
> 	int l;
> 	int r;
> 	int sign;
> 	char c;
> }re[10001];
> 
> 
> char str[10001];
> 
> int main()
> {
> 	int Case;
> 
> 	scanf("%d",&Case);
> 
> 	for( ; Case-- ; )
> 	{
> 		
> 
> 		scanf("%s",str);
> 
> 		deque<node> s;
> 		deque<node> que;
> 
> 		s.clear();
> 		int len = strlen(str);
> 		int i,j,k;
> 		node root;
> 		node p;
> 
> 		for( i=0 ; i<len ; i++ )
> 		{
> 			//re[i].c = str[i];
> 			//re[i].l = -1;
> 			//re[i].r = -1;
> 
> 			if( str[i]>='a'&&str[i]<='z' )
> 			{
> 				node tmp;
> 				tmp.c = str[i];
> 				tmp.l = -1;
> 				tmp.r = -1;
> 				tmp.sign = i;
> 				s.push_back(tmp);
> 				re[i] = tmp;
> 			}
> 			else
> 			{	
> 				node tmp;
> 				p.c = str[i];
> 				p.sign = i;
> 
> 				tmp = s.back();
> 				s.pop_back();
> 				p.l = tmp.sign;
> 
> 				tmp = s.back();
> 				s.pop_back();
> 				p.r = tmp.sign;
> 
> 				s.push_back( p );
> 				root = p;
> 
> 				re[i] = p;
> 			}
> 			
> 		}
> 
> 		que.clear();
> 
> 		que.push_back( root );
> 
> 		string res = "";
> 		//res.clear();
> 		node t;
> 
> 		//memset(flag,0,sizeof(flag));
> 
> 		for( ; !que.empty() ; )
> 		{
> 			t = que.front();
> 			res = t.c + res;
> 			que.pop_front();
> 
> 			if( t.r != -1 )
> 			{
> 				que.push_back( re[ t.r ] );
> 			}
> 
> 			if( t.l != -1 )
> 			{
> 				que.push_back( re[ t.l ] );
> 			}
> 
> 		}
> 
> 		printf("%s\n",res.c_str());
> 
> 	}
> }