Problem: A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters '+' and '1'. For example, sequences '(())()', '()', and '(()(()))' are balanced, while ')(', '(()', and '(()))(' are not.

You are given a binary string s of length n. Construct two balanced bracket sequences a and b of length n such that for all 1≤ i≤ n: 

  * if s_i=1, then a_i=b_i 
  * if s_i=0, then a_i≠ b_i 



If it is impossible, you should report about it.

Input

The first line contains a single integer t (1≤ t≤ 10^4) — the number of test cases.

The first line of each test case contains a single integer n (2≤ n≤ 2⋅ 10^5, n is even).

The next line contains a string s of length n, consisting of characters 0 and 1.

The sum of n across all test cases does not exceed 2⋅ 10^5.

Output

If such two balanced bracked sequences exist, output "YES" on the first line, otherwise output "NO". You can print each letter in any case (upper or lower).

If the answer is "YES", output the balanced bracket sequences a and b satisfying the conditions on the next two lines.

If there are multiple solutions, you may print any.

Example

Input


3
6
101101
10
1001101101
4
1100


Output


YES
()()()
((()))
YES
()()((()))
(())()()()
NO

Note

In the first test case, a="()()()" and b="((()))". The characters are equal in positions 1, 3, 4, and 6, which are the exact same positions where s_i=1.

In the second test case, a="()()((()))" and b="(())()()()". The characters are equal in positions 1, 4, 5, 7, 8, 10, which are the exact same positions where s_i=1.

In the third test case, there is no solution.

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;

/**
 * #
 *
 * @author pttrung
 */
public class C_Round_712_Div2 {
    public static long MOD = 1000000007;
    static int last;
    static long[][] dp;
    static boolean[][] check;

    public static void main(String[] args) throws FileNotFoundException {
        // PrintWriter out = new PrintWriter(new FileOutputStream(new File(
        // "output.txt")));
        PrintWriter out = new PrintWriter(System.out);
        Scanner in = new Scanner();
        int T = in.nextInt();
        for (int z = 0; z < T; z++) {
            int n = in.nextInt();
            String data = in.next();
            int one = 0;
            for (int i = 0; i < n; i++) {
                if (data.charAt(i) == '1') {
                    one++;
                }
            }
            if (one % 2 != 0) {
                out.println("NO");
            } else {
                int x = 0, y = 0;
                StringBuilder a = new StringBuilder();
                StringBuilder b = new StringBuilder();
                int cur = 0;
                boolean ok = true;
                for (int i = 0; i < n && ok; i++) {
                    if (data.charAt(i) == '1') {
                        if (cur * 2 < one) {
                            cur++;
                            x++;
                            y++;
                            a.append("(");
                            b.append("(");
                        } else {
                            if (x > 0 && y > 0) {
                                x--;
                                y--;
                                a.append(")");
                                b.append(")");
                            } else {
                                ok = false;

                            }
                        }
                    } else {
                        if (x >= y) {
                            if (x > 0) {
                                x--;
                                y++;
                                a.append("(");
                                b.append(")");
                            } else {
                                ok = false;
                            }
                        } else {
                            x++;
                            y--;
                            a.append(")");
                            b.append("(");
                        }
                    }
                }
                if (!ok) {
                    out.println("NO");
                } else {
                    out.println("YES");
                    out.println(a.toString());
                    out.println(b.toString());
                }
            }

        }
        out.close();
    }


    static class Node {
        int l, r, max = 0;
        Node left, right;

        Node(int l, int r) {
            this.l = l;
            this.r = r;
        }

        void update(int index, int val) {
            if (index > r || index < l) {
                return;
            }
            if (l == index && index == r) {
                max = Integer.max(max, val);
                return;
            }
            if (left == null) {
                int mid = (l + r) / 2;
                left = new Node(l, mid);
                right = new Node(mid + 1, r);
            }
            left.update(index, val);
            right.update(index, val);
            max = Integer.max(left.max, right.max);
        }

        int get(int lt, int rt) {
            if (lt > r || rt < l) {
                return 0;
            }
            if (lt <= l && r <= rt) {
                return max;
            }
            if (left == null) {
                return 0;
            }
            return Integer.max(left.get(lt, rt), right.get(lt, rt));
        }

    }


    public static int[] KMP(String val) {
        int i = 0;
        int j = -1;
        int[] result = new int[val.length() + 1];
        result[0] = -1;
        while (i < val.length()) {
            while (j >= 0 && val.charAt(j) != val.charAt(i)) {
                j = result[j];
            }
            j++;
            i++;
            result[i] = j;
        }
        return result;

    }

    public static boolean nextPer(int[] data) {
        int i = data.length - 1;
        while (i > 0 && data[i] < data[i - 1]) {
            i--;
        }
        if (i == 0) {
            return false;
        }
        int j = data.length - 1;
        while (data[j] < data[i - 1]) {
            j--;
        }
        int temp = data[i - 1];
        data[i - 1] = data[j];
        data[j] = temp;
        Arrays.sort(data, i, data.length);
        return true;
    }

    public static int digit(long n) {
        int result = 0;
        while (n > 0) {
            n /= 10;
            result++;
        }
        return result;
    }

    public static double dist(long a, long b, long x, long y) {
        double val = (b - a) * (b - a) + (x - y) * (x - y);
        val = Math.sqrt(val);
        double other = x * x + a * a;
        other = Math.sqrt(other);
        return val + other;

    }

    public static class Point implements Comparable<Point> {

        int x;
        int y;

        public Point(int start, int end) {
            this.x = start;
            this.y = end;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x &&
                    y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public int compareTo(Point o) {
            if (y != o.y) {
                return Integer.compare(y, o.y);
            }
            return Integer.compare(x, o.x);


        }
    }

    public static class FT {

        long[] data;

        FT(int n) {
            data = new long[n];
        }

        public void update(int index, long value) {
            while (index < data.length) {
                data[index] += value;
                index += (index & (-index));
            }
        }

        public long get(int index) {
            long result = 0;
            while (index > 0) {
                result += data[index];
                index -= (index & (-index));
            }
            return result;

        }
    }

    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static long pow(long a, long b) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }

        long val = pow(a, b / 2);
        if (b % 2 == 0) {
            return (val * val) % MOD;
        } else {
            return (val * ((val * a) % MOD)) % MOD;

        }
    }

    static class Scanner {

        BufferedReader br;
        StringTokenizer st;

        public Scanner() throws FileNotFoundException {
            // System.setOut(new PrintStream(new BufferedOutputStream(System.out), true));
            br = new BufferedReader(new InputStreamReader(System.in));
            //br = new BufferedReader(new InputStreamReader(new FileInputStream(new File("input.txt"))));
        }

        public String next() {

            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }

        public boolean endLine() {
            try {
                String next = br.readLine();
                while (next != null && next.trim().isEmpty()) {
                    next = br.readLine();
                }
                if (next == null) {
                    return true;
                }
                st = new StringTokenizer(next);
                return st.hasMoreTokens();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
    }
}