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.*;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;




//import jdk.javadoc.internal.doclets.toolkit.NestedClassWriter;
 
 
 
 
public class Codeforces {
	static String a,b;
	static class Node
	{
		int val;
		Node left;
		Node right;
		public Node(int x) {
			// TODO Auto-generated constructor stub
			this.val=x;
			this.left=null;
			this.right=null;
			}
	}
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        }
        int[] nextArray(int n)
        {
        	int arr[]=new int[n];
        	for(int i=0;i<n;i++)
        		arr[i]=nextInt();
        	return arr;
        }
    } 
	static String string;
	static int gcd(int a, int b)
    {
        // Everything divides 0 
        if (a == 0)
          return b;
        if (b == 0)
          return a;
      
        // base case
        if (a == b)
            return a;
      
        // a is greater
        if (a > b)
            return gcd(a-b, b);
        return gcd(a, b-a);
    }
	static long gcd(long a, long b)
    {
        // Everything divides 0 
   
        for(long i=2;i<=b;i++)
        {
        	if(a%i==0&&b%i==0)
        		return i;
        }
        return 1;
    }
	static int fac(int n)
	{
		int c=1;
		for(int i=2;i<n;i++)
		if(n%i==0)
			c=i;
		return c;
	}
	static boolean ab(int i,HashSet<Integer> hs,int n,int prev)
	{
		if(i==n)
			return true;
		int cur=2;
		while(i<4*n)
		{
			if(prev==-1)
			{
				hs.add(cur);
				if(ab(i+1, hs, n, cur))
				{
					
					string=cur+" "+string;
					return true;
				}
				else
					hs.remove(hs.size()-1);
			}
			else {
				if(!hs.contains(cur)&&gcd(cur, prev)>1)
				{
					hs.add(cur);
					Iterator<Integer> iterator=hs.iterator();
					int flag=0;
					while(iterator.hasNext())
					{
						int x=iterator.next();
						if(x%cur==0||cur%x==0)
						{
							flag=1;
							break;
						}
					}
						
					if(flag==0&&ab(i+1, hs, n, cur))
					{
					string=cur+" "+string;
					return true;
					}
					hs.remove(hs.size()-1);
				}
					
			}
			cur+=2;
		}
		return false;
	}
	static boolean check(String all,String ch,int i,int k,boolean flag)
	{
		//System.out.println(i+","+k);
		if(i==all.length()||ch.length()==k)
		{
			if(ch.length()==k&&flag)
				return true;
			return false;
		}
		
		for(int j=i;j<all.length();j++)
		{
			if(i>0&&j!=i&&ch.charAt(k)==all.charAt(j)&&check(all, ch, j+1,k+1, true))
				return true;
			else if(ch.charAt(k)==all.charAt(j)&&check(all, ch, j+1,k+1, flag))
				return true;
				
		}
		return false;
	}
	static int lcm(int a,int b)
	{
		for(int i=Math.min(a, b);i<=a*b;i++)
			if(i%a==0&&i%b==0)
				return i;
		return 0;
	}
	static int maxheight(char[][] ch,int i,int j,String[] arr)
	{
		int h=1;
		if(i==ch.length-1||j==0||j==ch[0].length-1)
			return 1;
		while(i+h<ch.length&&j-h>=0&&j+h<ch[0].length&&ch[i+h][j-h]=='*'&&ch[i+h][j+h]=='*')
		{
			String whole=arr[i+h];
			//System.out.println(whole.substring(j-h,j+h+1));
			if(whole.substring(j-h,j+h+1).replace("*","").length()>0)
				return h;
			h++;
		}
			
		return h;
	}
	static boolean all(BigInteger n)
	{
		BigInteger c=n;
		HashSet<Character> hs=new HashSet<>();
		while((c+"").compareTo("0")>0)
		{
			String d=""+c;
			char ch=d.charAt(d.length()-1);
			if(d.length()==1)
			{
				c=new BigInteger("0");
				
			}
			else
			c=new BigInteger(d.substring(0,d.length()-1));
			if(hs.contains(ch))
				continue;
			if(d.charAt(d.length()-1)=='0')
				continue;
			if(!(n.mod(new BigInteger(""+ch)).equals(new BigInteger("0"))))
				return false;
				hs.add(ch);
		}
		return  true;
	}
	
	static int cal(long n,long k)
	{
		System.out.println(n+","+k);
		if(n==k)
			return 2;
		if(n<k)
			return 1;
		if(k==1)
			return 1+cal(n, k+1);
		if(k>=32)
			return 1+cal(n/k, k);
		return 1+Math.min(cal(n/k, k),cal(n, k+1));
	}
	static Node buildTree(int i,int j,int[] arr)
	{
		if(i==j)
		{
			
			//System.out.print(arr[i]);
			return new Node(arr[i]);
		}
		int max=i;
		for(int k=i+1;k<=j;k++)
		{
			if(arr[max]<arr[k])
				max=k;
		}
		Node root=new Node(arr[max]);
		//System.out.print(arr[max]);
		if(max>i)
			root.left=buildTree(i, max-1, arr);
		else {
			root.left=null;
		}
		if(max<j)
			root.right=buildTree(max+1, j, arr);
		else {
			root.right=null;
		}
		return root;
	}
	static int height(Node root,int val)
	{
		if(root==null)
			return Integer.MAX_VALUE-32;
		if(root.val==val)
			return 0;
		if((root.left==null&&root.right==null))
			return Integer.MAX_VALUE-32;
		return Math.min(height(root.left, val), height(root.right, val))+1;
	}
	static void shuffle(int a[], int n) 
    { 
        for (int i = 0; i < n; i++) { 
  
            // getting the random index 
            int t = (int)Math.random() * a.length; 
  
            // and swapping values a random index 
            // with the current index 
            int x = a[t]; 
            a[t] = a[i]; 
            a[i] = x; 
        } 
    }
	static void sort(int[] arr )
	{
		shuffle(arr, arr.length);
		Arrays.sort(arr);
	}
	static int helper(int i,boolean flag,int n,int c,int val,int[][][] dp)
	{
		if(i<=0||i>=n+1)
		{
			c++;
			return 1;
		}
		int last=flag?1:0;
		if(dp[i][val][last]!=0)
			return dp[i][val][last];
		int ans=0;
		if(flag)
		{
			ans=helper(i+1, flag, n, c, val,dp);
			if(val>1)
			ans+=helper(i-1, !flag, n, c, val-1,dp);
		}
		else {
			ans=helper(i-1, flag, n, c, val,dp);
			if(val>1)
			ans+=helper(i+1, !flag, n, c, val-1,dp);
		}
		return dp[i][val][last]=ans;	
	}
	static boolean valid(char[] arr,int k)
	{
		int[] count=new int[26];
		for(int i=0;i<arr.length;i++)
			count[(int)arr[i]-'a']++;
		for(int i=0;i<26;i++)
			if(count[i]%k!=0)
				return false;
		return true;
	}
	static boolean helper(char[] text,int i,int o1,int c1,int o2,int c2,String temp1,String temp2,HashSet<String> hs)
	{
		if(i==text.length)
		{
			a=temp1;
			b=temp2;
			return true;
		}
		if(hs.contains(temp2+temp1)||hs.contains(temp1+temp2))
			return false;
		hs.add(temp1+temp2);
		hs.add(temp2+temp1);
		if(text[i]=='1')
		{
			if(o1<text.length/2&&o2<text.length/2&&helper(text, i+1, o1+1, c1, o2+1, c2, temp1+"(", temp2+"(", hs))
				return true;
			if(c1<o1&&c2<o2&&helper(text, i+1, o1, c1+1, o2, c2+1, temp1+")", temp2+")", hs))
				return true;
		}
		else {
			if(o1<text.length/2&&c2<o2&&helper(text, i+1, o1+1, c1, o2, c2+1, temp1+"(", temp2+")", hs))
				return true;
			if(o2<text.length/2&&c1<o1&&helper(text, i+1, o1, c1+1, o2+1, c2, temp1+")", temp2+"(", hs))
				return true;
		}
		return false;
	}
	static int compute(int c,int r)
	{
		if(r<c/2)
			r=c-r;
		int ans=1;
		for(int i=c;i>r;i--)
			ans*=i;
		int fac=fac(c-r);
		return ans/fac;
	}
public static void main(String[] args)throws IOException
{
	BufferedReader bReader=new BufferedReader(new InputStreamReader(System.in));
	FastReader fs=new FastReader();
	PrintWriter out=new PrintWriter(System.out);
	int T=fs.nextInt();
	StringBuilder sb=new StringBuilder();
	while(T-->0)
	{
		
		string="";
		int n=fs.nextInt();
		String text=fs.nextLine();
		int zero=text.length()-text.replace("0", "").length(),one=n-zero,c1=0;
		if(text.charAt(0)=='0'||text.charAt(n-1)=='0'||zero%2!=0)
		{
			sb.append("NO\n");
			continue;
		}
		StringBuilder sb1=new StringBuilder(),sb2=new StringBuilder();
		boolean prev=true;
		for(int i=0;i<n;i++)
		{
			if(text.charAt(i)=='1')
			{
				if(c1<one/2)
				{
					sb1.append("(");
					sb2.append("(");
				}
				else {
					sb1.append(")");
					sb2.append(")");
				}
				c1++;
			}
			else {
				if(prev)
				{
					sb1.append("(");
					sb2.append(")");
				}
				else {
					sb1.append(")");
					sb2.append("(");
				}
				prev=!prev;
			}
		}
		
		{
			sb.append("YES\n").append(sb1).append("\n").append(sb2).append("\n");
		}
		
	}
	System.out.println(sb);
 }
}