#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

string s;
const int N = 105;
int dp[N][N], from[N][N];
string rebuild(int l, int r) {
    // fprintf(stderr, "rebuild [%d, %d]\n", l, r);
    if (l > r) {
        return "";
    }
    if (l == r) {
        switch (s[l]) {
            case '(':
            case ')':
                return "()";
            case '[':
            case ']':
                return "[]";
        }
    }
    if (from[l][r] == -1) {
        // fprintf(stderr, "haha[%d, %d]\n", l, r);
        return s[l] + rebuild(l + 1, r - 1) + s[r];
    }
    return rebuild(l, from[l][r]) + rebuild(from[l][r] + 1, r);
}
int main() {
    int T;
    scanf("%d", &T);
    getchar();
    while (T--) {
        memset(dp, 0x3f, sizeof dp);
        memset(from, -1, sizeof from);
        getline(cin, s), getline(cin, s);
        int n = s.length();
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
            dp[i + 1][i] = 0;
        }
        for (int len = 2; len <= n; len++) {
            for (int l = 0; (l + len - 1) < n; l++) {
                int r = l + len - 1;
                if ((s[l] == '(' && s[r] == ')') || (s[l] == '[' && s[r] == ']')) {
                    dp[l][r] = dp[l + 1][r - 1];
                    from[l][r] = -1; // -1 means transition from dp[l + 1][j - 1].
                }
                for (int k = l; k < r; k++) {
                    if (dp[l][k] + dp[k + 1][r] < dp[l][r]) {
                        dp[l][r] = dp[l][k] + dp[k + 1][r];
                        from[l][r] = k;
                    }
                }
            }
        }
        cout << rebuild(0, n - 1) << "\n\n";
    }
    return 0;
}

感觉应该是输入输出格式的问题毕竟测了一些东西都是过了的。