DreamGrid 有 $n$ 位同学，编号从 $1$ 到 $n$。其中一些是男生，另一些是女生。每位同学都有一些宝石，具体来说，第 $i$ 位同学有 $i$ 颗宝石。

DreamGrid 想将这些同学分成四个组 $G_1, G_2, G_3$ 和 $G_4$，使得：

• 每位同学恰好属于一个组。
• $G_1$ 和 $G_2$ 只包含女生，$G_3$ 和 $G_4$ 只包含男生。
• $G_1$ 和 $G_3$ 中的宝石总数等于 $G_2$ 和 $G_4$ 中的宝石总数。

你的任务是帮助 DreamGrid 对他的同学进行分组，以满足上述条件。注意，你可以让某些组为空。

输入格式

输入包含多个测试用例。第一行是一个整数 $T$，表示测试用例的数量。

对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示同学的人数。

第二行包含一个由 $0$ 和 $1$ 组成的字符串 $s$ ($|s| = n$)。令 $s_i$ 为字符串 $s$ 中的第 $i$ 个字符。如果 $s_i = 1$，则第 $i$ 位同学是男生；如果 $s_i = 0$，则第 $i$ 位同学是女生。

保证所有 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出一个仅由 $\{1, 2, 3, 4\}$ 组成的字符串。字符串的第 $i$ 个字符表示第 $i$ 位同学所属的组。如果存在多个有效答案，你可以输出其中任意一个；如果不存在有效答案，则输出 “-1”（不含引号）。

样例

样例输入 1

5
1
1
2
10
3
101
4
0000
7
1101001

样例输出 1

-1
-1
314
1221
3413214