Parenthesis Selection

Dr. Juraj has discovered a new kind of fundamental particle called a parenthesision, which can exist in one of two states: open or close. Using his particle accelerator, he created an ensemble of $t$ sequences, each consisting of $2n$ particles. These particles are organized into $n$ pairs — every two consecutive particles form a pair. Note that within a pair the two particles (each representing a bracket) may be in different states, or they may be identical (both open or both close). When a sequence is observed, one particle from each pair will collapse into a definite state (either '(' for open or ')' for close).

The problem is as follows: For each of the $t$ sequences, determine whether it is possible to select exactly one bracket from each of the $n$ pairs such that the resulting sequence (of length $n$) is a valid parentheses sequence. A sequence is valid if it is empty, or if it can be written in the form ( (A) ) or ( AB ), where both (A) and (B) are valid sequences.

If a valid selection exists, you must output one way to choose from each pair so that the resulting sequence is valid. In the output, for each pair, output a '1' if you select the first bracket (i.e. the one at odd index) or '2' if you select the second bracket (i.e. the one at even index).

inputFormat

The input begins with an integer $T$, the number of test cases. For each test case, the first line contains an integer $n$, indicating that there are $n$ pairs (i.e. the sequence length is $2n$). The following line contains a string $S$ of length $2n$, consisting solely of the characters '(' and ')'. The $i$-th pair consists of the characters $S_{2i-1}$ and $S_{2i}$.

outputFormat

For each test case, if there exists a valid selection, output two lines. On the first line, print “YES”. On the second line, print a string of length $n$ where the $i$-th character is '1' if you chose the first bracket of the $i$-th pair, or '2' if you chose the second bracket. If no valid selection exists, simply output a single line with “NO”.

sample

1
4
()))((()

YES
1112