#include <stdio.h>
#include<string.h>
int function(char *,char,int,int);
int preced(char);
int main(void) {
int t;
scanf("%d",&t);
while(t>0)
{
int n;
scanf("%d",&n);
char ch[n];
scanf("%s",&ch);
char stack[n],postfix[n];
int i,tos=-1,k=0;
tos=function(stack,’#’,tos,1);
for(i=0;i<n;i++)
{
if((ch[i]>=‘A’ &&ch[i]<=‘Z’))
{
postfix[k]=ch[i];
k++;
}
else if(ch[i]==’(’)
{
tos=function(stack,ch[i],tos,1);
}
else if(ch[i]=='^')
tos=function(stack,ch[i],tos,1);
else if (ch[i]==')'){
while(stack[tos] != '('){
postfix[k]=stack[tos];
k++;
tos--;
}
tos--;
}
else{
while(preced(ch[i]) <= preced(stack[tos])) {
postfix[k]=stack[tos];
tos--;
k++;
}
tos=function(stack,ch[i],tos,1);
}
}
while(stack[tos] != '#') {
postfix[k]=stack[tos];
tos--;
k++;
}
for(i=0;i<k;i++)
{
printf("%c",postfix[i]);
}
printf("\n");
t--;
}
return 0;
}
int function(char stack[],char ch,int tos,int p)
{
if(p==1)
{
tos++;
stack[tos]=ch;
return tos;
}
if(p==2)
{
tos--;
return tos;
}
}
int preced(char ch) {
if(ch == ‘+’ || ch == ‘-’) {
return 1;
}else if(ch == ‘*’ || ch == ‘/’) {
return 2;
}else if(ch == ‘^’) {
return 3;
}else {
return 0;
}
}