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.

Difficulty: competition

Starter code:

Solutions:
for __ in range(int(input())):
    n = int(input())
    s = list(map(int, input()))
    r = [0] * n
    for i in range(10):
        left_lim = 0
        for j, c in enumerate(s):
            if c < i: left_lim = j + 1
        prv = [-1, -1, -1]
        flg = True
        for j, c in enumerate(s):
            r[j] = 1 if c < i or (c == i and j >= left_lim) else 2
            if c < prv[r[j]]: flg = False; break
            prv[r[j]] = c
        if flg:
            print(''.join(map(str, r)))
            break
    if not flg:
        print('-')

def calc(X):
    for i in range(10):
        RET = []
        h = i
        l = 0
        for j in range(len(X)):
            if X[j] >= h:
                h = X[j]
                RET.append("2")
            elif l <= X[j] <= i:
                l = X[j]
                RET.append("1")
            else:
                break
        else:
            print("".join(RET))
            break
    else:
        print("-")

T = int(input())
for _ in range(T):
    N = int(input())
    A = [int(a) for a in input()]
    calc(A)



def main():
    from sys import stdin, stdout
    input1 = stdin.readline
    print1 = stdout.write
    for _ in range(int(input1())):
        input1()
        t = tuple(map(int, input1().rstrip('\n')))
        for mid in range(10):
            ans = []
            lasts = [0, 0, 0]
            lasts[2] = mid
            for ti in t:
                if ti < lasts[1]:
                    break
                if ti < lasts[2]:
                    color = 1
                else:
                    color = 2
                ans.append(str(color))
                lasts[color] = ti
            else:
                if lasts[1] == mid:
                    print1(''.join(ans) + '\n')
                    break
        else:
            print1('-\n')


main()


import sys
l1 = []
l2 = []


def iss():
    for i in range(len(l1) - 1):
        if l1[i+1] < l1[i]:
            return False
    for i in range(len(l2) - 1):
        if l2[i+1] < l2[i]:
            return False
    return True






for q in range(int(input())):
    n = int(sys.stdin.readline())
    data = [int(i) for i in sys.stdin.readline().strip()]
    done = False
    for d in range(10):
        mnl2 = -1
        mxl1 = -1
        same = []
        l1 = []
        l2 = []
        ans = ['0']*n
        for i in range(n):
            f = data[i]
            if f > d:
                l2.append(f)
                ans[i] = '2'
               
                if mnl2 == -1:
                    mnl2 = i
            elif f < d:
                ans[i] = '1'
                l1.append(f)
                mxl1 = i
            else:
                same.append(i)
        # print(d, same, l1, l2, iss(), mxl1, mnl2)
        if not iss():
            continue
        good = True
        for s in same:
            if s > mxl1:
                ans[s] = '1'
            elif s < mnl2:
                ans[s] = '2'
            else:
                good = False
                break
        if not good:
            continue
        sys.stdout.write("".join(ans) + '\n')
        done = True
        break
    if not done:
        sys.stdout.write('-\n')

        




#!/usr/bin/env python3
import sys

def rint():
    return list(map(int, sys.stdin.readline().split()))
#lines = stdin.readlines()

t = int(input())
for tt in range(t):
    n = int(input())
    d_str = input()
    d = []
    for i in range(n):
        d.append(int(d_str[i]))
    #print(d)
    di=[]
    for i in range(n):
        di.append(i)
    #print(d)
    for b in range(10):
        one_min = -1
        two_min = -1
        not_ok = 0
        ans = []
        for i in range(n):
            if d[i] < b:
                if d[i] < one_min:
                    not_ok = 1
                    break
                one_min = d[i]
                ans.append(1)

            elif d[i] > b:
                if d[i] < two_min:
                    not_ok = 1
                    break
                two_min = d[i]
                ans.append(2)
            else:
                if b >= two_min:
                    two_min = b
                    ans.append(2)
                elif b >= one_min:
                    one_min = b
                    ans.append(1)
                else:
                    not_ok = 1
                    break
        if not_ok != 1:
            print("".join(map(str,ans)))
            break
    else:
        print("-")







t = int(input())

for i in range(t):
    n = int(input())
    s = input().rstrip()
    sint = [int(item) for item in s]
    for div in range(10):
        is_ok = True
        ga = []; gb = []
        a = 0; b = div 
        for i, item in enumerate(sint):
            # b should take
            if item > div:
                if b > item:
                    is_ok = False
                    break
                else:
                    gb.append(i)
                    b = item
            elif item == div:
                if b == div:
                    gb.append(i)
                else:
                    a = item
                    ga.append(i)
            else:
                if a > item:
                    is_ok = False
                    break
                else:
                    ga.append(i)
                    a = item
        if is_ok:
            break
    if is_ok:
        ans = [1] * n
        for item in gb:
            ans[item] = 2
        print("".join([str(item) for item in ans]))
    else:
        print("-")

T = int(input())
for t in range(T):
    N = int(input())
    sequence = input().strip()
    digits = set(sequence)
    isPossible = False
    number = ""
    ret = []
    for minTwo in digits:
        ret = []
        one = str(0)
        two = minTwo
        for i, digit in enumerate(sequence):
            if digit < one:
                break
            elif digit >= two:
                two = digit
                ret.append("2")
            elif digit > minTwo:
                break
            else:
                one = digit
                ret.append("1")
            if i == len(sequence) - 1:
                isPossible = True
        if isPossible:
            break
    if isPossible:
        ret = "".join(ret)
        print(ret)
    else:
        print("-")


for t in range(int(input())):
    n = int(input())
    ans = [2]*n
    d = list(map(int,input()))
    k = d[0]
    ind_1 = -1
    for i in range(n):
        if d[i] > k:
            k = d[i]
        if d[i] < k:
            ans[i] = 1
            if ind_1 == -1:
                ind_1 = i
    for i in range(ind_1):
        if d[i] <= d[ind_1]:
            ans[i] = 1
    itog = []
    for i in range(n):
        if ans[i] == 1:
            itog.append(d[i])
    for i in range(n):
        if ans[i] == 2:
            itog.append(d[i])
    for i in range(1,n):
        if itog[i] < itog[i-1]:
            print('-')
            break
    else:
        print(''.join(map(str,ans)))





import sys
def main():
    def input():
        return sys.stdin.readline()[:-1]
    t = int(input())
    for z in range(t):
        flag = 0
        n = int(input())
        s = [int(x) for x in input()]
        for limit in range(10):
            ans = [0 for k in range(n)]
            p = 0
            for now in range(limit+1):
                for k in range(p,n):
                    if s[k] == now:
                        p = k
                        ans[k] = 1
            p = 0
            for now in range(limit,10):
                for k in range(p,n):
                    if s[k] == now and ans[k] == 0:
                        p = k
                        ans[k] = 2
            if 0 not in ans:
                flag = 1
                print(*ans,sep="")
                break
        if flag == 0:
            print("-")

def __starting_point():
    main()

__starting_point()