You are given a sequence of $n$ digits $d_1d_2 \dots d_{n}$. You need to paint all the digits in two colors so that:  each digit is painted either in the color $1$ or in the color $2$;  if you write in a row from left to right all the digits painted in the color $1$, and then after them all the digits painted in the color $2$, then the resulting sequence of $n$ digits will be non-decreasing (that is, each next digit will be greater than or equal to the previous digit). 

For example, for the sequence $d=914$ the only valid coloring is $211$ (paint in the color $1$ two last digits, paint in the color $2$ the first digit). But $122$ is not a valid coloring ($9$ concatenated with $14$ is not a non-decreasing sequence).

It is allowed that either of the two colors is not used at all. Digits painted in the same color are not required to have consecutive positions.

Find any of the valid ways to paint the given sequence of digits or determine that it is impossible to do.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10000$) — the number of test cases in the input.

The first line of each test case contains an integer $n$ ($1 \le n \le 2\cdot10^5$) — the length of a given sequence of digits.

The next line contains a sequence of $n$ digits $d_1d_2 \dots d_{n}$ ($0 \le d_i \le 9$). The digits are written in a row without spaces or any other separators. The sequence can start with 0.

It is guaranteed that the sum of the values ​​of $n$ for all test cases in the input does not exceed $2\cdot10^5$.


-----Output-----

Print $t$ lines — the answers to each of the test cases in the input.

If there is a solution for a test case, the corresponding output line should contain any of the valid colorings written as a string of $n$ digits $t_1t_2 \dots t_n$ ($1 \le t_i \le 2$), where $t_i$ is the color the $i$-th digit is painted in. If there are several feasible solutions, print any of them.

If there is no solution, then the corresponding output line should contain a single character '-' (the minus sign).


-----Example-----
Input
5
12
040425524644
1
0
9
123456789
2
98
3
987

Output
121212211211
1
222222222
21
-



-----Note-----

In the first test case, $d=040425524644$. The output $t=121212211211$ is correct because $0022444$ (painted in $1$) concatenated with $44556$ (painted in $2$) is $002244444556$ which is a sorted sequence of $n$ given digits.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\nl1 = []\nl2 = []\n\n\ndef iss():\n    for i in range(len(l1) - 1):\n        if l1[i+1] < l1[i]:\n            return False\n    for i in range(len(l2) - 1):\n        if l2[i+1] < l2[i]:\n            return False\n    return True\n\n\n\n\n\n\nfor q in range(int(input())):\n    n = int(sys.stdin.readline())\n    data = [int(i) for i in sys.stdin.readline().strip()]\n    done = False\n    for d in range(10):\n        mnl2 = -1\n        mxl1 = -1\n        same = []\n        l1 = []\n        l2 = []\n        ans = [\'0\']*n\n        for i in range(n):\n            f = data[i]\n            if f > d:\n                l2.append(f)\n                ans[i] = \'2\'\n               \n                if mnl2 == -1:\n                    mnl2 = i\n            elif f < d:\n                ans[i] = \'1\'\n                l1.append(f)\n                mxl1 = i\n            else:\n                same.append(i)\n        # print(d, same, l1, l2, iss(), mxl1, mnl2)\n        if not iss():\n            continue\n        good = True\n        for s in same:\n            if s > mxl1:\n                ans[s] = \'1\'\n            elif s < mnl2:\n                ans[s] = \'2\'\n            else:\n                good = False\n                break\n        if not good:\n            continue\n        sys.stdout.write("".join(ans) + \'\\n\')\n        done = True\n        break\n    if not done:\n        sys.stdout.write(\'-\\n\')\n\n        \n\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13809