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.awt.*;
import java.io.*;
import java.util.List;
import java.util.*;

public class Main {

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;

        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(
                    new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    } else {
                        continue;
                    }
                }
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0,
                    BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }
//
//

    //    static class TreeNode {
//        int val;
//        TreeNode left,right;
//        TreeNode(int val){
//            this.val=val;left=null;right=null;
//        }
//    }
//    static TreeNode maxx(int start,int end,int[] arr){
//        if(start>end){
//            return null;
//        }
//        int ind=0;
//        int max=-1;
//        for(int j=start;j<=end;j++){
//            if(arr[j]>max){
//                max=arr[j];
//                ind=j;
//            }
//        }
//        TreeNode jj=new TreeNode(arr[ind]);
//        jj.left=maxx(start,ind-1,arr);
//        jj.right=maxx(ind+1,end,arr);
//        return jj;
//
//    }
//    static void dfs(TreeNode root,int dep){
//        if(root==null){
//            return;
//        }
//        ans[hashMap.get(root.val)]=dep;
//        dfs(root.left,dep+1);
//        dfs(root.right,dep+1);
//    }
//    static int[] ans;
//   static HashMap<Integer,Integer> hashMap;
//   static class pont{
//       int val,index;
//       pont(int val,int index){
//           this.val=val;
//           this.index=index;
//       }
//   }
//   static class compr implements Comparator<pont>{
//       public int compare(pont a,pont b){
//           return a.val-b.val;
//       }
//   }
//    static class poin{
//       int src;
//       long val;
//       poin(int src,long val){
//           this.src=src;
//           this.val=val;
//       }
//    }
//
//    static double maxx(int flag,String s,String t,int k){
//
//       if(flag==0){
//
//           StringBuilder stringBuilder = new StringBuilder(s.substring(0,s.length()-1));
//           double ans= 0.0;
//           for(int j=1;j<10;j++){
//               StringBuilder str=new StringBuilder(stringBuilder);
//               str.append(j);
//
//               ans=(double)((double)ans+(double)maxx(1,str.toString(),t,k));
//           }
//           return ans;
//       }
//       else if(flag==1){
//
//           StringBuilder stringBuilder = new StringBuilder(t.substring(0,t.length()-1));
//           double ans= 0.0;
//           for(int j=1;j<10;j++){
//               StringBuilder str=new StringBuilder(stringBuilder);
//               str.append(j);
//               ans=(double)((double)ans+(double)maxx(2,s,str.toString(),k));
//           }
//           return ans;
//
//       }
//       else{
//           long[] count=new long[10];
//           long taka=0;
//           long[] tot=new long[10];
//
//           for(int j=0;j<s.length();j++){
//               int a=Integer.parseInt(String.valueOf(s.charAt(j)));
//               count[a]++;
//               tot[a]++;
//           }
//           for(int j=1;j<10;j++){
//               taka=(long)((long)taka+(long)((long)Math.pow(10,count[j])*(long)j));
//           }
//           long aoki=0;
//           count=new long[10];
//           for(int j=0;j<t.length();j++){
//               int a=Integer.parseInt(String.valueOf(t.charAt(j)));
//               count[a]++;
//               tot[a]++;
//           }
//           for(int j=1;j<10;j++){
//               aoki=(long)((long)aoki+(long)((long)Math.pow(10,count[j])*(long)j));
//           }
//           if(aoki>=taka){
//               return 0;
//           }else{
//               if(t.charAt(t.length()-1)==s.charAt(s.length()-1)){
//                   double kk=(double)k-(double)tot[Integer.parseInt(String.valueOf(t.charAt(t.length()-1)))]+(double)2;
//                   return (double)((double)((double)(kk)*(double)(kk-(double)1))/(double)((double)1*((double)9*(double)k-(double)8)*(double)((double)9*(double)k-(double)9)));
//
//               }else{
//                   double kk=(double)k-(double)tot[Integer.parseInt(String.valueOf(t.charAt(t.length()-1)))]+(double)1;
//                   double kk2=(double)k-(double)tot[Integer.parseInt(String.valueOf(s.charAt(s.length()-1)))]+(double)1;
//                   return (double)(((double)((double)1*(double)kk)*(double)(kk2))/(double)((double)1*((double)9*(double)k-(double)8)*(double) ((double)9*(double)k-(double)9)));
//               }
//           }
//
//       }
//
//
//    }
//
//   static void sieveOfEratosthenes(int n)
//    {
//        boolean prime[] = new boolean[n + 1];
//        for (int i = 0; i <= n; i++)
//            prime[i] = true;
//
//        for (int p = 2; p * p <= n; p++)
//        {
//            if (prime[p] == true)
//            {
//                for (int i = p * p; i <= n; i += p)
//                    prime[i] = false;
//            }
//        }
//
//        for (int i = 2; i <= n; i++)
//        {
//            if (prime[i] == true)
//                treeMap.put(i,0);
//        }
//    }
//    static TreeMap<Integer,Integer> treeMap;
    static class comp implements Comparator<Point> {
        public int compare(Point a, Point b) {
            if (b.y == a.y) {
                return a.x - b.x;
            }
            return b.y - a.y;
        }
    }

    static boolean ff = false;

    //    static void maxx(int ind,int l,int r,int d,int u,int n)
//    {
//        if(ind==4){
//            if(l<0 || r<0 || u<0 || d<0){
//                return;
//            }
//            ff=true;
//            return;
//        }
//        if(ind==0){
//            if(l==n){
//                maxx(ind+1,l-2,r,d-1,u-1,n);
//            }else if(l==n-1){
//                maxx(ind+1,l-1,r,d-1,u,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l-1,r,d,u-1,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//
//        }else if(ind==1){
//            if(r==n){
//                maxx(ind+1,l,r-2,d-1,u-1,n);
//            }else if(r==n-1){
//                maxx(ind+1,l,r-1,d-1,u,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l,r-1,d,u-1,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//
//        }else if(ind==2){
//            if(d==n){
//                maxx(ind+1,l-1,r-1,d-2,u,n);
//            }else if(d==n-1){
//                maxx(ind+1,l-1,r,d-1,u,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l,r-1,d-1,u,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//
//        }else{
//            if(u==n){
//                maxx(ind+1,l-1,r-1,d,u-2,n);
//            }else if(u==n-1){
//                maxx(ind+1,l-1,r,d,u-1,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l,r-1,d,u-1,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//        }
//    }
//    static void filereader() throws IOException{
//        FileReader fileReader=new FileReader("input.txt");
//        int ch;
//        String str="";
//        StringBuilder stringBuilder=new StringBuilder();
//        while ((ch=fileReader.read())!=-1)
//            stringBuilder.append((char)ch);
//
//        fileReader.close();
//        StringBuilder ans=new StringBuilder();
//        FileWriter fw=new FileWriter("output.txt");
//        for(int j=0;j<ans.length();j++){
//            fw.write(ans.charAt(j));
//        }
//        fw.close();
//    }
    static class point {
        int w, v;

        point(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    static class compp implements Comparator<point> {
        public int compare(point a, point b) {
            return b.v - a.v;
        }
    }

    //    static int cal(int ind,String s,String x,int val){
//        if(ind>=s.length()){
//            if(val%7==0){
//                return 1;
//            }else{
//                return 0;
//            }
//        }
//        if(aa[ind][val]!=-1){
//            return aa[ind][val];
//        }
//
//        if(x.charAt(ind)=='A'){
//            int ii=Integer.parseInt(String.valueOf(s.charAt(ind)));
//            return aa[ind][val]=Math.min( cal(ind+1,s,x,(val*10)%7  ),cal(ind+1,s,x, (val*10+ii)%7 )  );
//        }else{
//            int ii=Integer.parseInt(String.valueOf(s.charAt(ind)));
//            return aa[ind][val]=Math.max( cal(ind+1,s,x,(val*10)%7  ),cal(ind+1,s,x, (val*10+ii)%7 )  );
//        }
//
//    }
//    static int aa[][];
    static List<Integer> findprime(int n) {
        List<Integer> primes = new ArrayList<>();
        boolean[] prime = new boolean[n];
        for (int j = 1; j < prime.length; j++) {
            prime[j] = true;
        }
        for (int j = 2; j * j < prime.length; j++) {
            if (!prime[j]) {
                continue;
            }
            for (int i = j * j; i < prime.length; i = i + j) {
                prime[i] = false;
            }
        }
        for (int j = 2; j < prime.length; j++) {
            if (prime[j]) {
                primes.add(j);
            }
        }
        return primes;
    }

    //    static long calculateWays(int ind,int bit,int[] primes,long a,long b,int[] flags){
//
//        long num=(long)((long)ind+(long)a);
//        if(num>b){
//            return 1;
//        }
//        if(aaa[ind][bit]!=-1){
//            return aaa[ind][bit];
//        }
//
//        long tot=0;
////        int flag=0;
////        int bitt=bit;
////        for(int j=0;j<primes.length;j++){
////            int jj= (int)bit & (int)Math.pow(2,j);
////
////            if(jj!=0 && num%(long)primes[j]==0 ){
////                flag=1;
////                break;
////            }
////            if( num%(long)primes[j]==0 ){
////                bitt=(int)bitt | (int)Math.pow(2,j);
////
////            }
////        }
//        int jj=(int)(flags[ind] & (int)bit);
//        if( jj==0){
//            tot=(long)((long)tot+(long)calculateWays(ind+1,bit | flags[ind],primes,a,b,flags));
//            tot=(long)((long)tot+(long)calculateWays(ind+1,bit,primes,a,b,flags));
//
//        }else{
//            tot=(long)((long)tot+(long)calculateWays(ind+1,bit,primes,a,b,flags));
//        }
//
//        return aaa[ind][bit]=tot;
//    }
    static long[][] aaa;

    static long maxx(String str, int n, long val) {

        if (hashMap.get(str) != null) {
            return hashMap.get(str);
        }
        long tot = 0;
        if (str.equals("")) {
            for (int j = 1; j <= 9; j++) {
                tot = tot + maxx(str + String.valueOf(j), n, val);
            }
            hashMap.put(str, tot);

            return tot;
        } else {
            String ss = str + str;
            if (Long.parseLong(ss) > val) {
                return 0;
            }
            if (str.length() == n) {
                return 1;
            }
            for (int j = 0; j <= 9; j++) {
                tot = tot + maxx(str + String.valueOf(j), n, val);
            }
            hashMap.put(str, tot);
            return tot;
        }

    }

    static class poi {
        int freq, occur, num;

        poi(int freq, int occur, int num) {
            this.freq = freq;
            this.num = num;
            this.occur = occur;
        }
    }

    static class poii {
        int day, tot;

        poii(int day, int tot) {
            this.day = day;
            this.tot = tot;
        }
    }

    static class comp2 implements Comparator<poii> {
        public int compare(poii a, poii b) {
            return a.tot - b.tot;
        }
    }

    static class comp1 implements Comparator<poi> {
        @Override
        public int compare(poi o1, poi o2) {
            if (o2.occur == o1.occur) {
                return o1.freq - o2.freq;
            }
            return o1.occur - o2.occur;
        }
    }

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

    static HashMap<String, Long> hashMap;

    static class poit {
        int freq, val;

        poit(int freq, int val) {
            this.freq = freq;
            this.val = val;
        }
    }

    static class com implements Comparator<poit> {
        public int compare(poit a, poit b) {
            return b.freq - a.freq;
        }
    }


    static int maxx(int ind,String str,int prev,int x,int y){
        if(ind>=str.length()){
            return 0;}
        if(aa[ind][prev]!=Integer.MAX_VALUE){
            return aa[ind][prev];}
        if(str.charAt(ind)=='?' ){
            if(ind>0){
                if(prev==1){
                    if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
                             return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y)+x+y );

                    }
                    else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
                        return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+x,maxx(ind+1,str,2,x,y)+x );

                    }
                    else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
                        return aa[ind][prev]=  Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y)+x );
                    }
                    else{
                        return aa[ind][prev]=Math.min(maxx( ind+1,str,1,x,y ),maxx(ind+1,str,2,x,y)+x);
                    }

                }
                else{
                    if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
                        return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+y,maxx(ind+1,str,2,x,y)+y );

                    }
                    else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
                        return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+x+y,maxx(ind+1,str,2,x,y) );

                    }
                    else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
                        return aa[ind][prev]=  Math.min(maxx(ind+1,str,1,x,y)+y,maxx(ind+1,str,2,x,y) );
                    }
                    else{
                        return aa[ind][prev]=Math.min(maxx( ind+1,str,1,x,y )+y,maxx(ind+1,str,2,x,y));
                    }
                }
            }
            else{
                if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
                    return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y)+x );

                }
                else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
                    return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+x,maxx(ind+1,str,2,x,y) );

                }
                else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
                    return aa[ind][prev]=  Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y) );
                }
                else{
                    return aa[ind][prev]=0;
                }
            }
        }else if(str.charAt(ind)=='C'){
            if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
                return aa[ind][prev]=maxx(ind+1,str,1,x,y);

            }
            else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
                return aa[ind][prev]=maxx(ind+1,str,1,x,y)+x;

            }
            else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
                return aa[ind][prev]=  maxx(ind+1,str,1,x,y);
            }
            else{
                return aa[ind][prev]=0;
            }
        }
        else{
            if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
                return aa[ind][prev]=maxx(ind+1,str,2,x,y)+y;

            }
            else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
                return aa[ind][prev]=maxx(ind+1,str,2,x,y);

            }
            else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
                return aa[ind][prev]=  maxx(ind+1,str,2,x,y);
            }
            else{
                return aa[ind][prev]=0;
            }
        }
    }
    static int[][] aa;
    static int totalCost(int[] arr,int[] arr1,int n){
        HashMap<Integer,Integer> has=new HashMap<>();
        for(int i=0;i<n;i++){

            has.put(arr[i],i );

        }
        Arrays.sort(arr1);
        int tot=0;
        for(int i=0;i<n-1;i++){
            tot=tot+has.get(arr1[i])-i+1;
            int tta=has.get(arr1[i]);
            for(int j=tta;j>=i;j-- ){
                has.put(arr[j],tta-j+i );

            }
            int low=i;
            int high=tta;
            while(low<high){
                int temp=arr[low];
                arr[low]=arr[high];
                arr[high]=temp;
                low++;high--;
            }

        }
        return tot;

    }
    static boolean fff=false;
    static HashSet<String> hashSet=new HashSet<>();
    static void maxx(int ind,int[] arr,HashSet<Integer> has,int n,String str,int cost){
        if(ind==n){
            int to=totalCost(arr,arr,n);
            if(to==cost){
                fff=true;
            }
            return;
        }
        if(hashSet.contains(str)){
            return ;
        }
        for(int j=1;j<=n;j++){
            if(!has.contains(j)){
                arr[ind]=j;
                has.add(j);
                maxx(ind+1,arr,has,n,str+String.valueOf(j),cost);
                has.remove(j);
            }
            if(ff){
                return;
            }
        }
    }
    static long maxx(int ind,int n,int flag,int k){
        if(ind>n || ind<0 || k==1){
            return 0;
        }
        if(flag==1 && ind==0){
            return 0;
        }
        if(aaaa[ind][flag][k]!=-1) {
            return aaaa[ind][flag][k];
        }
        if(flag==0){
            return aaaa[ind][flag][k]=(long)(maxx(ind-1,n,1,k-1)+(long)1+maxx(ind+1,n,0,k))%(long)mod;
        }
        else{
            return aaaa[ind][flag][k]=(long)(maxx(ind+1,n,0,k-1)+(long)1+maxx(ind-1,n,1,k))%(long)mod;
        }

    }
    static long[][][] aaaa;
    static long mod=(long)((long)Math.pow(10,9)+(long)7);
    public static void main(String[] args) throws IOException {
        BufferedReader scanner=new BufferedReader(new InputStreamReader(System.in));
        int t= Integer.parseInt(scanner.readLine().trim());
        for(int j=0;j<t;j++) {
            int n = Integer.parseInt(scanner.readLine().trim());
            String str = scanner.readLine().trim();
            int co1 = 0, co2 = 0;
            boolean flag = false;
            if (str.charAt(0) == '0' || str.charAt(str.length() - 1) == '0') {
                System.out.println("NO");
                continue;
            }
            for (int i = n - 1; i >= 0; i--) {
                if (str.charAt(i) == '0') {
                    co1++;
                } else {
                    co2++;
                }
            }
            if (co1 % 2 == 1 || co2 % 2 == 1) {
                System.out.println("NO");
                continue;
            }
            StringBuilder s1 = new StringBuilder();
            StringBuilder s2 = new StringBuilder();
            int ii = 0;

            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == '1') {
                    if (ii < co2 / 2) {
                        s1.append('(');
                        s2.append('(');
                    } else {
                        s1.append(')');
                        s2.append(')');
                    }
                    ii++;
                } else {
                    if(flag){
                        s1.append('(');
                        s2.append(')');
                        flag=false;
                    }else{
                        s1.append(')');
                        s2.append('(');
                        flag=true;
                    }
                }
            }

            System.out.println("YES");
            System.out.println(s1.toString());
            System.out.println(s2.toString());

        }



//            String str= scanner.readLine().trim();
//            if(str.length()<=1 ){
//                System.out.println("NO");
//            }else{
//                StringBuilder stringBuilder=new StringBuilder();
//                int ii=-1;
//                for(int i=0;i<str.length();i++){
//                    if(str.charAt(i)!='a' ){
//                        ii=i;break;
//                    }
//                }
//                if(ii==-1){
//                    System.out.println("NO");
//                }else{
//                    if(str.length()%2==0){
//                        for (int k = 0; k < str.length(); k++) {
//
//
//
//                            if (k == str.length() - ii - 1) {
//                                if(k==str.length()/2){
//                                    stringBuilder.append(str.charAt(k));
//                                    stringBuilder.append('a');
//                                    continue;
//                                }
//                                stringBuilder.append('a');
//
//                            }
//                            stringBuilder.append(str.charAt(k));
//                        }
//                    }else {
//                        for (int k = 0; k < str.length(); k++) {
//                            stringBuilder.append(str.charAt(k));
//                            if (k == str.length() - ii - 1) {
//                                stringBuilder.append('a');
//
//                            }
//
//
//                        }
//                    }
//                    System.out.println("YES");
//                    System.out.println(stringBuilder.toString());
//
//                }
//
//            }

        }








    }