Let us define a regular brackets sequence in the following way:

1. Empty sequence is a regular sequence.
2. If S is a regular sequence, then (S) and [S] are both regular sequences.
3. If A and B are regular sequences, then AB is a regular sequence.

For example, all of the following sequences of characters are regular brackets sequences:

(), [], (()), ([]), ()[], ()[()]

And all of the following character sequences are not:

(, [, ), )(, ([)], ([(]

Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a₁a₂...a_n is called a subsequence of the string b₁b₂...b_m, if there exist such indices 1 ≤ i₁ < i₂ < ... < i_n ≤ m, that a_j=b_ij for all 1 ≤ j ≤ n.

Input 

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

 

 

The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.

Output 

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

 

 

Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.

Sample Input 

1([(]

Sample Output 

()[()] 紫书上有详解＋代码，就不废话了直接贴代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int maxn = 110; 6 char s[maxn]; 7 int d[maxn][maxn]; 8 int n; 9 inline bool match(char a,char b){10     if((a=='('&&b==')')||(a=='['&&b==']')) return true;11     else return false;12 }13 void dp(){14     for(int i=0;i
        
         =0;i--){20         for(int j=i+1;j
         
          j) return;32     if(i==j){33         if(s[i]=='('||s[i]==')') printf("()");34         else printf("[]");35         return;36     }37     int ans=d[i][j];38     if(match(s[i],s[j])&&ans==d[i+1][j-1]){39         printf("%c",s[i]);print(i+1,j-1);printf("%c",s[j]);40         return;41     }42     for(int k=i;k