Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 4033
CONTINUE...?

Time Limit: 1 Second      Memory Limit: 65536 KB      Special Judge

DreamGrid has $n$ classmates numbered from $1$ to $n$. Some of them are boys and the others are girls. Each classmate has some gems, and more specifically, the $i$-th classmate has $i$ gems.

DreamGrid would like to divide the classmates into four groups $G_1$, $G_2$, $G_3$ and $G_4$ such that:

• Each classmate belongs to exactly one group.

• Both $G_1$ and $G_2$ consist only of girls. Both $G_3$ and $G_4$ consist only of boys.

• The total number of gems in $G_1$ and $G_3$ is equal to the total number of gems in $G_2$ and $G_4$.

Your task is to help DreamGrid group his classmates so that the above conditions are satisfied. Note that you are allowed to leave some groups empty.

#### Input

There are multiple test cases. The first line of input is an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$) -- the number of classmates.

The second line contains a string $s$ ($|s| = n$) consisting of 0 and 1. Let $s_i$ be the $i$-th character in the string $s$. If $s_i = 1$, the $i$-th classmate is a boy; If $s_i = 0$, the $i$-th classmate is a girl.

It is guaranteed that the sum of all $n$ does not exceed $10^6$.

#### Output

For each test case, output a string consists only of {1, 2, 3, 4}. The $i$-th character in the string denotes the group which the $i$-th classmate belongs to. If there are multiple valid answers, you can print any of them; If there is no valid answer, output "-1" (without quotes) instead.

#### Sample Input

5
1
1
2
10
3
101
4
0000
7
1101001


#### Sample Output

-1
-1
314
1221
3413214


Author: LIN, Xi
Source: The 15th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
Submit    Status