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:
/*
ID: abdelra29
LANG: JAVA
TASK: skidesign
*/
import java.util.*;
import java.math.*;
import java.io.*; 
 public class B{
static int[] dx = new int[]{-1,0,1,0};
    static int[] dy = new int[]{0,1,0,-1};
    static FastReader scan=new FastReader();
   public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
  static ArrayList<Pair>es;
  static LinkedList<Integer>edges[];
  static Set<Pair>edges2[][];

   static boolean prime[];
   static void sieve(int n) 
    { 
        
        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; 
            } 
        } 
          
        
    }      
     public static int lowerBound(int[] array, int length, int value) {
        int low = 0;
        int high = length;
        while (low < high) {
            final int mid = (low + high) / 2;
            //checks if the value is less than middle element of the array
            if (value <= array[mid]) {
                high = mid;
            } else {
                low = mid+1 ;
            }
        }
        return low;
    }
    public static int upperBound(int[] array, int length, int value) {
        int low = 0;
        int high = length;
        while (low < high) {
            final int mid = low+(high-low) / 2;
            if ( array[mid]>value) {
                high = mid ;
            } else {
                low = mid+1;
            }
        }
        return low;
    }
static long mod(long x,long y)
    {
        if(x<0)
            x=x+(-x/y+1)*y;
        return x%y;
    }    
     static boolean isPowerOfTwo(long n) 
    { 
        if (n == 0) 
            return false; 
  
        while (n != 1) { 
            if (n % 2 != 0) 
                return false; 
            n = n / 2; 
        } 
        return true; 
    } 

  
   
static boolean isprime(long x)
           {
            for(long i=2;i*i<=x;i++)
                if(x%i==0)
                    return false;
                return true;
           }


static int dist(int x1,int y1,int x2,int y2){
return Math.abs(x1-x2)+Math.abs(y1-y2);
}


    static long cuberoot(long x)
    {
        long lo = 0, hi = 1000005;
        while(lo<hi)
        {
            long m = (lo+hi+1)/2;
            if(m*m*m>x)
                hi = m-1;
            else
                lo = m;
        }
        return lo;
    }
     public static int log2(int N) 
    { 
  
        // calculate log2 N indirectly 
        // using log() method 
        int result = (int)(Math.log(N) / Math.log(2)); 
  
        return result; 
    } 
  
    
   
       static long gcd(long a, long b) {
    if(a!=0&&b!=0)
        while((a%=b)!=0&&(b%=a)!=0);
    return a^b;
}
    static long LCM(long a,long b){
    return (Math.abs(a*b))/gcd(a,b);
   }
   static int mid;
   public static class comp1 implements Comparator<Pair>{  
public int compare(Pair o1,Pair o2){
    return (int)(o1.y-o2.y);
}
  }

     public static class comp2 implements Comparator<Pair>{  
public int compare(Pair o1,Pair o2){
 
return (int)((o1.x+o1.y*mid)-(o2.x+o2.y*mid));
}
  }
 static boolean can(int m,int s)
 {
    return (s>=0&&s<=m*9);
 }
   static boolean collinear(long x1, long y1, long x2,  
                          long y2, long x3, long y3) 
{
    long a = x1 * (y2 - y3) +  
                x2 * (y3 - y1) +  
                x3 * (y1 - y2); 
                if(a==0)
                    return true;
                return false;
}

static int ceil(int a,int b)
{
    if(a%b!=0)
        return (a/b)+1;
    else return a/b;
}
static boolean vis[]=new boolean[(int)1e5+5];
static int cnt=0;
static int count1[];
 static void numberOfNodes(int s, int e) 
    { 
        count1[s] = 1; 
        for(Integer u: edges[s]) 
        { 
            // condition to omit reverse path 
            // path from children to parent 
            if(u == e) 
                continue; 
              
            // recursive call for DFS 
            numberOfNodes(u ,s); 
              
            // update count[] value of parent using  
            // its children 
            count1[s] += count1[u]; 
        } 
    } 
    static int res=0;
static void dfs(int x)
{
    vis[x]=true;
    cnt++;
    for(int v:edges[x])
        if(!vis[v]){
            if(count1[v]%2==0)
                res++;
            dfs(v);
        }
}

public static void main(String[] args)  throws Exception 
{
    /*int xx=253;
    for(int i=1;i*i<=xx;i++)
    {
        if(xx%i==0)
        {
            System.out.println(i);
            System.out.println(xx/i);
        }
    }*/
//java.util.Scanner scan=new java.util.Scanner(new File("mootube.in"));
// PrintWriter out = new PrintWriter (new FileWriter("mootube.out"));
//scan=new FastReader("skidesign.in");
//out = new PrintWriter ("skidesign.out");
//System.out.println(3^2);
//System.out.println(19%4);
   //StringBuilder news=new StringBuilder("ab");
   //news.deleteCharAt(1);
   //news.insert(0,'c');
   //news.deleteCharAt(0);
   //System.out.println(news);
   //System.out.println(can(2,15));
    //System.out.println(LCM(2,2));
  // System.out.println(31^15);
 //System.out.println("");
   //System.out.println(824924296372176000L>(long)1e16);
int tt=1;
//rec(2020);

//int st=scan.nextInt();
//System.out.println(calc(91));
//sieve(21000);

//SNWNSENSNNSWNNW

   // System.out.println(set.remove(new Pair(1,1)));
//System.out.println(count("cccccccccccccccccccccccccooooooooooooooooooooooooodddddddddddddeeeeeeeeeeeeeeeeeeeeeeeeeffffffffffffforrrrrrrrrrrrrcesssssssssssss","codeforces"));
  //S0ystem.out.println(isPowerOfTwo(446265625L));
//System.out.println("daaa".compareTo("bccc"));
//System.out.println(2999000999L>1999982505L);
//System.out.println("?bac?bac??a?a?a?abac????abacab?ca?a".length());
 //tt=scan.nextInt();
//String ok="ABDC";
//System.out.println(ok.substring(2));
//System.out.println(2000000000/2);
tt=scan.nextInt();
//System.out.println(isprime(23335));
//int T=1;
  outer:while(tt-->0)
 {
    int n=scan.nextInt();
    StringBuilder s=new StringBuilder(scan.next());
    
    TreeSet<Integer>ones=new TreeSet<Integer>();
    TreeSet<Integer>zeros=new TreeSet<Integer>();
    StringBuilder res1=new StringBuilder("");
    StringBuilder res2=new StringBuilder("");
    int cnt1=0,cnt2=0;
    if(s.charAt(0)=='0'||s.charAt(s.length()-1)=='0')
    {
        out.println("NO");
        continue outer;
    }
    //101101
    res1.append("(");
    res2.append("(");
    cnt1++;
    cnt2++;
    for(int i=1;i<s.length()-1;i++)
    {
        if(s.charAt(i)=='0'&&s.charAt(i+1)=='0')
        {
            res1.append("()");
            res2.append(")(");
            i++;
        }
        else if(s.charAt(i)=='1'&&s.charAt(i+1)=='1')
        {
            if(i+1==n-1&&cnt1-2>=0&&cnt2-2>=0)
            {
                res1.append("))");
                res2.append("))");
                cnt1-=2;
                cnt2-=2;
                i++;
            }
            else {
            res1.append("()");
            res2.append("()");
            i++;
        }
        }
        else if(s.charAt(i)=='0')
        {
            if(cnt1<cnt2)
            {
                cnt1++;
                res1.append("(");
                res2.append(")");
                cnt2--;
            }
            else 
            {
                 cnt1--;
                res1.append(")");
                res2.append("(");
                cnt2++;

            }

        }
        else 
        {

            if((cnt1==0||cnt2==0)||(cnt1-1==0&&cnt2-1==0&&s.charAt(i+1)=='0'))
            {
                //out.println(i);
                res1.append("(");
                res2.append("(");
                cnt1++;
                cnt2++;
            }
            else 
            {
                 res1.append(")");
                res2.append(")");
                cnt1--;
                cnt2--;
            }
        }
    }
    if(res1.length()<n){
    res1.append(")");
    res2.append(")");
    cnt1--;
    cnt2--;
}
//    out.println(res1);
   // out.println(res2);
    if(cnt1!=0||cnt2!=0)
    {
       // out.println("FUCK");
        out.println("NO");
        continue outer;
    }
    out.println("YES");
    out.println(res1);
    out.println(res2);


  

  

}
out.close();

}

static class dsu{
    static int id[]=new int[101];
    dsu()
    {
        for(int i=0;i<101;i++)
            id[i]=i;
    }
    static int find(int x)
    {
        if(x==id[x])
            return x;
        return find(id[x]);
    }
    static void connect(int i,int j)
    {
        i=find(i);
        j=find(j);
        id[i]=j;
    }
    static boolean is(int i,int j)
    {
        return find(i)==find(j);
    }
}
static long binexp(long a,long n,long mod)
{
    if(n==0)
       return 1;
    long res=binexp(a,n/2,mod)%mod;
    res=res*res;
    if(n%2==1)
        return (res*a)%mod;
    else 
        return res%mod;
}
static class special{
    Pair x;
    Pair y;
    special(Pair x,Pair y)
    {
      this.x=new Pair(x.x,x.y);
      this.y=new Pair(y.x,y.y);
    }   
      @Override
        public int hashCode() {
            return (int)(x.x + 31 * y.y);
        }
        public boolean equals(Object other)
    {
        if(other instanceof special)
        {
            special e =(special)other;
            return this.x.x==e.x.x && this.x.y==e.x.y && this.y.x==e.y.x && this.y.y==e.y.y;
        }
        else return false;
    }
}
static long powMod(long base, long exp, long mod) {
       if (base == 0 || base == 1) return base;
       if (exp == 0) return 1;
       if (exp == 1) return base % mod;
       long R = powMod(base, exp/2, mod) % mod;
       R *= R;
       R %= mod;
       if ((exp & 1) == 1) {
           return base * R % mod;
       }
       else return R % mod;
   }
 public static  long pow(long b, long e) {
            long r = 1;
            while (e > 0) {
                if (e % 2 == 1) r = r * b ;
                b = b * b;
                e >>= 1;
            }
            return r;
        }

private static void sort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int object : arr) list.add(object);
        Collections.sort(list);
        for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
    }
 public static class FastReader {
        BufferedReader br;
        StringTokenizer root;
        
 
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        FastReader(String filename)throws Exception
        {

            br=new BufferedReader(new FileReader(filename));
        }
 
        String next() {
            while (root == null || !root.hasMoreTokens()) {
                try {
                    root = new StringTokenizer(br.readLine());
                } catch (Exception addd) {
                    addd.printStackTrace();
                }
            }
            return root.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        double nextDouble() {
            return Double.parseDouble(next());
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
 
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (Exception addd) {
                addd.printStackTrace();
            }
            return str;
        }
         public int[] nextIntArray(int arraySize) {
            int array[] = new int[arraySize];
 
            for (int i = 0; i < arraySize; i++) {
                array[i] = nextInt();
            }
 
            return array;
        }
}
public static class Pair implements Comparable<Pair>{
         long x;
         long y;
         long ab;
        
        long z;
        public Pair(){}
        public Pair(long x1, long y1,long z) {
            x=x1;
            y=y1;
            this.z=z;
        }
        public Pair(long x1, long y1) {
            x=x1;
            y=y1;
            this.ab=x+y;
        
        }
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result +(int) x;
            result = prime * result + (int)y;
            return result;
        }
        public String toString() {
            return x + " " + y;
        }
        @Override
        public boolean equals(Object o){
            if (o == this) return true;
            if(o==null)
                return false;
            if (o.getClass() != getClass()) return false;
            Pair t = (Pair)o;
            return t.x == x && t.y == y;
        }
        public  int compareTo(Pair o)
        {
            return (int)(y-o.y);
        }
}

}