#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;#define up(i,x,y) for(i=x;i<=y;i++)#define down(i,x,y) for(i=x;i>=y;i--)#define mem(a,b) memset(a,b,sizeof(a))#define w(a) while(a)char str[105];int t,len,dp[105][105],mark[105][105],pos[105];void dfs(int i,int j){ if(mark[i][j]==-1) { pos[i]=pos[j]=1; dfs(i+1,j-1); } else if(mark[i][j]>=0) { dfs(i,mark[i][j]); dfs(mark[i][j]+1,j); } return;}int main(){ int l,i,j,k; scanf("%d%*c%*c",&t); while(t--) { gets(str); len=strlen(str); if(!len) { printf("n"); if(t) printf("n"); continue; } up(i,0,len-1) up(j,0,len-1) { mark[i][j]=-2; dp[i][j]=0; } mem(pos,0); i=j=l=0; w(l<len) { if(i==j) { i++,j++; if(j==len) i=0,l++,j=l; continue; } if((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[j]==']')) { up(k,i,j-1) { if(dp[i][j]<dp[i][k]+dp[k+1][j]) { mark[i][j]=k; dp[i][j]=dp[i][k]+dp[k+1][j]; } } if(dp[i][j]<dp[i+1][j-1]+1) { mark[i][j]=-1; dp[i][j]=dp[i+1][j-1]+1; } } else { up(k,i,j-1) { if(dp[i][j]<dp[i][k]+dp[k+1][j]) { mark[i][j]=k; dp[i][j]=dp[i][k]+dp[k+1][j]; } } } i++,j++; if(j==len) { l++; i=0; j=l; } } dfs(0,len-1); up(i,0,len-1) { if(pos[i]==1) printf("%c",str[i]); else if(str[i]=='('||str[i]==')') printf("()"); else printf("[]"); } printf("n"); if(t) { printf("n"); getchar(); } } return 0;}
