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: MEDIUM
Tags: Greedy algorithms

Implementation

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from __future__ import division, print_function
import bisect

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		indexes = [[] for i in range(10)]
		for j in range(n):
			indexes[ord(s[j]) - ord('0')].append(j)
		for i in range(10):
			x = str(i)
			if len(indexes[i]) == 0:
				continue
			break
		stack = []
		stack.extend(indexes[i])
		for j in range(i + 1, 10):
			if len(indexes[j]) == 0:
				continue
			else:
				idx = bisect.bisect_left(indexes[j], stack[-1])
				if idx < len(indexes[j]):
					stack.extend(indexes[j][idx:])
					if idx != 0:
						break
				else:
					break
		nodes = [2] * n
		for item in stack:
			nodes[item] = 1
		left = []
		right = []
		for i in range(n):
			if nodes[i] == 1:
				left.append(s[i])
			else:
				right.append(s[i])
		left.extend(right)
		flag = 0
		for i in range(1, n):
			if left[i] < left[i - 1]:
				flag = 1
				break
		if flag == 0:
			print(*nodes, sep='')
		else:
			print('-')
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def readnumbers(zero=0):
	conv = ord if py2 else lambda x: x
	A = []
	numb = zero
	sign = 1
	i = 0
	s = sys.stdin.buffer.read()
	try:
		while True:
			if s[i] >= b'0'[0]:
				numb = 10 * numb + conv(s[i]) - 48
			elif s[i] == b'-'[0]:
				sign = -1
			elif s[i] != b'\r'[0]:
				A.append(sign * numb)
				numb = zero
				sign = 1
			i += 1
	except:
		pass
	if s and s[-1] >= b'0'[0]:
		A.append(sign * numb)
	return A
main()


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, list(input())))
	ms = [1] * n
	m = s[-1]
	for i in range(n - 2, -1, -1):
		if m < s[i]:
			ms[i] = 2
		else:
			m = min(m, s[i])
	mans = []
	f = 1
	m2 = -1
	for i in range(n):
		if ms[i] == 2:
			mans.append(2)
			if f:
				m2 = s[i]
				f = 0
		elif m2 < s[i] and m2 != -1:
			mans.append(2)
		else:
			mans.append(1)
	t1 = []
	t2 = []
	for i in range(n):
		if mans[i] == 1:
			t1.append(s[i])
		else:
			t2.append(s[i])
	if t1 == sorted(t1) and t2 == sorted(t2) and (len(t2) == 0 or len(t1) == 0 or t2[0] >= t1[-1]):
		print(''.join(list(map(str, mans))))
	else:
		print('-')


t = int(input())
while t > 0:
	n = int(input())
	lst = list(map(int, input().strip()))
	lst2 = lst.copy()
	lst2.sort()
	a = []
	b = []
	c = 0
	ind_l = [2] * n
	ind = 0
	for i in lst:
		if i == lst2[c]:
			a.append(i)
			ind_l[ind] = 1
			c += 1
		ind += 1
	for i in lst:
		if c < n and i == lst2[c]:
			b.append(i)
			c += 1
	if len(a) + len(b) < n:
		print('-')
	else:
		for i in ind_l:
			print(i, end='')
		print()
	t -= 1


from io import BytesIO, IOBase
from math import sqrt
import sys, os
from os import path
inpl = lambda : list(map(int, input().split()))
inpm = lambda : map(int, input().split())
inpi = lambda : int(input())
inp = lambda : input()
(rev, ra, l) = (reversed, range, len)
P = print
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def B(n):
	return bin(n).replace('0b', '')

def factors(n):
	arr = []
	for i in ra(2, int(sqrt(n)) + 1):
		if n % i == 0:
			arr.append(i)
			if i * i != n:
				arr.append(int(n / i))
	return arr

def dfs(arr, n):
	pairs = [[i + 1] for i in ra(n)]
	vis = [0] * (n + 1)
	for i in ra(l(arr)):
		pairs[arr[i][0] - 1].append(arr[i][1])
	pairs[arr[i][1] - 1].append(arr[i][0])
	comp = []
	for i in ra(n):
		stack = [pairs[i]]
		temp = []
		if vis[stack[-1][0]] == 0:
			while len(stack) > 0:
				if vis[stack[-1][0]] == 0:
					temp.append(stack[-1][0])
					vis[stack[-1][0]] = 1
					s = stack.pop()
					for j in s[1:]:
						if vis[j] == 0:
							stack.append(pairs[j - 1])
				else:
					stack.pop()
			comp.append(temp)
	return comp
from bisect import bisect_left as bl
from bisect import bisect_right as br
import sys, operator, math, operator
from collections import Counter
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
import random
tc = inpi()
while tc:
	tc -= 1
	n = inpi()
	li = list(inp())
	for i in ra(n):
		li[i] = [int(li[i]), i]
	li.sort()
	ans = [0] * n
	ans[li[0][1]] = 1
	(start, upper) = (li[0][1], float('inf'))
	(tr, sol) = (True, True)
	for i in ra(1, n):
		if li[i][1] > start and li[i][0] <= upper:
			ans[li[i][1]] = 1
			start = li[i][1]
		elif tr:
			ans[li[i][1]] = 2
			start1 = li[i][1]
			upper = li[i][0]
			tr = False
		elif li[i][0] >= upper and li[i][1] > start1:
			ans[li[i][1]] = 2
			start1 = li[i][1]
		else:
			sol = False
			break
	if sol:
		P(*ans, sep='')
	else:
		P('-')


def check(sep):
	global paint
	last1 = -1
	last2 = -1
	for i in range(n):
		si = int(s[i])
		if si < sep:
			if si < last1:
				return False
			paint[i] = '1'
			last1 = si
		elif si > sep:
			if si < last2:
				return False
			paint[i] = '2'
			last2 = si
		elif si >= last2:
			paint[i] = '2'
			last2 = si
		else:
			paint[i] = '1'
			last1 = si
	return True
T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	ok = False
	for i in range(10):
		paint = [0] * n
		if check(i):
			print(''.join(paint))
			ok = True
			break
	if not ok:
		print('-')


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	br = 0
	s1 = sorted(s)
	ans = ['2'] * len(s)
	i = 0
	while br < 2 and i != len(s1):
		for j in range(len(s)):
			if i == len(s):
				break
			if s1[i] == s[j]:
				i += 1
				if br == 0:
					ans[j] = '1'
		br += 1
	if i == len(s):
		print(''.join(ans))
	else:
		print('-')


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input()))
	numsarr = [[] for _ in range(10)]
	for (i, num) in enumerate(nums):
		numsarr[num].append(i)
	arr1 = []
	arr2 = []
	fl = False
	for (i, arr) in enumerate(numsarr):
		if fl:
			break
		for j in arr:
			if (not arr1 or arr1[-1] <= j) and (not arr2 or nums[arr2[0]] >= nums[j]):
				arr1.append(j)
			elif not arr2 or arr2[-1] <= j:
				arr2.append(j)
			else:
				print('-')
				fl = True
				break
		if fl:
			break
	if fl:
		continue
	ans = [2] * n
	for i in arr1:
		ans[i] = 1
	for i in arr2:
		ans[i] = 2
	print(*ans, sep='')


def color(d, n):
	col = [1] * n
	i = 1
	while i < n:
		if d[i][1] < d[i - 1][1]:
			break
		i += 1
	end1 = d[i - 1][1]
	if i < n:
		pivot = d[i][0]
		col[i] = 2
	i += 1
	while i < n:
		if d[i][1] < d[i - 1][1]:
			if d[i - 1][0] > pivot:
				return '-'
			else:
				j = 1
				while d[i - j][1] > end1:
					col[i - j] = 1
					j += 1
				if d[i][1] < d[i - j][1]:
					return '-'
		col[i] = 2
		i += 1
	colOrig = [None] * n
	for ((_, i), c) in zip(d, col):
		colOrig[i] = c
	return ''.join(map(str, colOrig))
t = int(input())
for _ in range(t):
	n = int(input())
	d = [(int(x), i) for (i, x) in enumerate(input())]
	d.sort()
	print(color(d, n))


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, list(input())))
		a = []
		for x in range(n):
			a.append([arr[x], x])
		a.sort()
		firstone = []
		secondone = []
		prev = a[0][1]
		chk = 0
		for x in range(n):
			if chk == 1:
				if prev == a[x][0]:
					continue
				secondone.append(a[x][1])
			elif a[x][1] >= prev:
				firstone.append(a[x][1])
				prev = a[x][1]
			else:
				chk = 1
				y = x
				while y < n and a[x][0] == a[y][0]:
					if a[y][1] >= prev:
						firstone.append(a[y][1])
						prev = a[y][1]
					else:
						secondone.append(a[y][1])
					y += 1
				prev = a[x][0]
		ans = [0 for x in range(n)]
		for x in firstone:
			ans[x] = 1
		for y in secondone:
			ans[y] = 2
		temp1 = []
		temp2 = []
		for x in range(n):
			if ans[x] == 1:
				temp1.append(arr[x])
			else:
				temp2.append(arr[x])
		temp = temp1 + temp2
		if sorted(temp) == temp:
			print(*ans, sep='')
		else:
			print('-')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys

def main():
	t = int(sys.stdin.readline())
	for test in range(t):
		n = int(sys.stdin.readline())
		a = list(sys.stdin.readline())
		f = False
		for x in range(10):
			br = x
			ar = -1
			seq = []
			for i in range(n):
				v = int(a[i])
				if v >= br:
					seq += ['2']
					br = v
				elif v >= ar:
					seq += ['1']
					ar = v
				else:
					seq = []
					break
			if seq and ar <= x:
				f = True
				break
		if f:
			sys.stdout.write(''.join(seq) + '\n')
		else:
			sys.stdout.write('-\n')
main()


def solve():
	n = int(input().strip())
	ds = [int(x) for x in input().strip()]
	assert len(ds) == n
	colors = []
	j = 0
	for i in range(1, len(ds)):
		if ds[i] < ds[i - 1]:
			j = i
			break
	if j == 0:
		print(''.join(('1' for _ in ds)))
		return
	max_one = ds[j]
	min_two = 9
	max_two = 0
	for d in ds[:j + 1]:
		if d <= ds[j]:
			colors.append('1')
		else:
			colors.append('2')
			min_two = min(d, min_two)
			max_two = max(d, max_two)
	assert min_two > max_one
	for d in ds[j + 1:]:
		if d < max_one:
			print('-')
			return
		elif d >= max_two:
			max_two = d
			colors.append('2')
		elif d <= min_two:
			colors.append('1')
			max_one = d
		else:
			print('-')
			return
	print(''.join(colors))

def main():
	t = int(input().strip())
	for _ in range(t):
		solve()
main()


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	s1 = sorted(s)
	s2 = s1
	(z, f, t) = ([], [], [])
	e = 1
	j = 0
	for i in s:
		if int(i) < int(s2[j]) and i != s2[j]:
			print('-')
			e = 0
			break
		if i != s2[j]:
			z.append('2')
			t.append(i)
		else:
			z.append('1')
			f.append(i)
			j += 1
	if e and f + t == s1:
		print(''.join(z))
	else:
		print('-')


from collections import Counter

def f(s):
	s = list(map(int, list(s)))
	seq = sorted(list(set(s)))
	ans = [-1] * len(s)
	ind = 0
	cmin = seq[0]
	ll = 0
	cnt = Counter(s)
	cmax = -float('inf')
	for i in range(len(s)):
		if s[i] == cmin:
			cnt[s[i]] -= 1
			ans[i] = 1
			if cnt[s[i]] == 0:
				ind += 1
				if ind < len(seq):
					cmin = seq[ind]
		elif s[i] >= cmin:
			if ll == 0:
				seq = seq[:seq.index(s[i]) + 1]
				ll = 1
			cnt[s[i]] -= 1
			ans[i] = 2
			cmax = max(s[i], cmax)
	if ans.count(-1):
		print('-')
		return ''
	check = True
	l = []
	r = []
	for i in range(len(ans)):
		if ans[i] == 1:
			l.append(s[i])
		else:
			r.append(s[i])
	t = l + r
	if t != sorted(t):
		check = False
	if check == False:
		print('-')
		return ''
	else:
		print(*ans, sep='')
for i in range(int(input())):
	a = input()
	s = input()
	f(s)


import sys
input = sys.stdin.readline
t = 1
t = int(input())
for _ in range(t):
	n = int(input())
	a = input()[:-1]
	ans = [-1] * n
	b = []
	for i in a:
		b.append(i)
	b.sort()
	index = n - 1
	two = n - 1
	one = n - 1
	while two >= 0 and index >= 0:
		if a[two] == b[index]:
			ans[two] = 2
			index -= 1
		two -= 1
	while one >= 0 and index >= 0:
		if a[one] == b[index]:
			ans[one] = 1
			index -= 1
		one -= 1
	if index != -1:
		print('-')
	else:
		for i in ans:
			print(i, end='')
		print()


import sys

def rint():
	return map(int, sys.stdin.readline().split())
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]))
	di = []
	for i in range(n):
		di.append(i)
	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)
			elif 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('-')


from collections import Counter
for _ in range(int(input())):
	(n, s) = (int(input()), input())
	copy = sorted(s)
	dp = Counter()
	pt = 0
	ok = True
	for i in range(n):
		if s[i] == copy[pt]:
			dp[i] = 1
			pt += 1
	for i in range(n):
		if pt >= n:
			break
		if dp[i] == 0 and s[i] == copy[pt]:
			dp[i] = 2
			pt += 1
		elif dp[i] == 0:
			ok = False
			break
	if ok:
		print(''.join([str(dp[i]) for i in range(n)]))
	else:
		print('-')


tests = int(input())
for t in range(tests):
	n = int(input())
	arr = list(map(int, list(input())))
	max_left = [arr[0]] * n
	max_right = [arr[n - 1]] * n
	min_left = [arr[0]] * n
	min_right = [arr[n - 1]] * n
	for i in range(1, n):
		max_left[i] = max(max_left[i - 1], arr[i])
		min_left[i] = min(min_left[i - 1], arr[i])
	for i in range(n - 2, -1, -1):
		max_right[i] = max(max_right[i + 1], arr[i])
		min_right[i] = min(min_right[i + 1], arr[i])
	listArr = [2] * n
	minToFind = min_right[0]
	maxV = -1
	for i in range(n):
		if arr[i] == minToFind:
			listArr[i] = 1
			if i < n - 1:
				minToFind = min_right[i + 1]
				if maxV != -1 and minToFind > maxV:
					break
		elif maxV == -1:
			maxV = arr[i]
	isValid = True
	maxV = -1
	for i in range(n):
		if listArr[i] == 2:
			if arr[i] < maxV:
				isValid = False
			maxV = arr[i]
	if isValid == False:
		print('-')
		continue
	print(*listArr, sep='')


T = int(input())
for t in range(T):
	n = int(input())
	d_og = [int(i) for i in str(input())]
	d = [i for i in d_og]
	flag = False
	c = [i for i in ''.join('-' * n)]
	d.sort()
	i = 0
	for k in range(2):
		flag = False
		j = 0
		while i < n and j < n:
			while d[i] != d_og[j] or c[j] != '-':
				j = j + 1
				if j >= n:
					flag = True
					break
			if flag:
				break
			c[j] = str(k + 1)
			i = i + 1
			j = j + 1
	if '-' in c:
		print('-')
	else:
		print(''.join(c))


import math
import sys
import collections

def getdict(n):
	d = {}
	if type(n) is list:
		for i in n:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	else:
		for i in range(n):
			t = ii()
			if t in d:
				d[t] += 1
			else:
				d[t] = 1
	return d

def sieve(n):
	r = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			r.append(p)
	return r

def cdiv(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
n = ii()
for i in range(n):
	t = ii()
	d = [int(x) for x in input()]
	sd = sorted(d)
	i = 0
	ans = [0] * t
	for j in range(t):
		if d[j] == sd[i]:
			ans[j] = 1
			i += 1
	for j in range(t):
		if i < t and d[j] == sd[i] and (ans[j] == 0):
			ans[j] = 2
			i += 1
	print(''.join(map(str, ans))) if i == t else print('-')


import sys
input = sys.stdin.readline

def solve(n, D):
	E = sorted(D)
	Ans = [0] * n
	idx = 0
	for (i, d) in enumerate(D):
		if d == E[idx]:
			idx += 1
			Ans[i] = 1
	for (i, d) in enumerate(D):
		if Ans[i]:
			continue
		if d != E[idx]:
			return ['-']
		idx += 1
		Ans[i] = 2
	return Ans
t = int(input())
for _ in range(t):
	n = int(input())
	D = list(map(int, list(input().strip())))
	print(*solve(n, D), sep='')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, list(input())))
	(q1, min1) = (n, float('inf'))
	for q in range(n - 1, -1, -1):
		if a[q] > min1:
			q1 = q
		else:
			min1 = a[q]
	if q1 == n:
		print('1' * n)
	else:
		(s, last) = ([1] * q1, a[q1])
		s.append(2)
		(d1, d2) = (a[:q1], [a[q1]])
		for q in range(q1 + 1, n):
			if a[q] >= last:
				s.append(2)
				d2.append(a[q])
				last = a[q]
			else:
				s.append(1)
				d1.append(a[q])
		d1 += d2
		for q in range(1, n):
			if d1[q] < d1[q - 1]:
				print('-')
				break
		else:
			print(''.join(list(map(str, s))))


from collections import defaultdict as dd
t = int(input())
while t:
	d = dd(int)
	s = ''
	n = int(input())
	res = ['2'] * n
	l = list(map(int, input().strip()))
	for i in range(n):
		d[l[i]] = i
	ll = set(l)
	ll = list(ll)
	ll.sort()
	i = 0
	j = 0
	mi = 100000000
	while j < n and i < len(ll):
		if d[ll[i]] < j:
			break
		if ll[i] == l[j] and l[j] <= mi:
			res[j] = '1'
		elif l[j] < mi:
			mi = l[j]
		if j == d[ll[i]]:
			i += 1
		j += 1
	lol = 0
	mx = -1
	mx1 = -1
	for i in range(n):
		if res[i] == '1':
			if l[i] < mx:
				lol = 1
				break
			else:
				mx = l[i]
		if res[i] == '2':
			if l[i] < mx1:
				lol = 1
				break
			else:
				mx1 = l[i]
	if lol == 1:
		print('-')
	else:
		print(''.join(res))
	t -= 1


import sys
import os
from io import IOBase, BytesIO

def main():
	for tc in range(int(input())):
		n = int(input())
		d = input()
		arr = [0] * n
		for i in range(n):
			arr[i] = int(d[i])
		ans = 0
		for x in range(1, 11):
			f = 0
			(one, two, o, t) = ([], [], [], [])
			chk = [1] * n
			for i in range(n):
				if arr[i] > x:
					f = 1
				if arr[i] < x:
					one.append(arr[i])
					o.append(arr[i])
					chk[i] = 1
				elif arr[i] > x:
					two.append(arr[i])
					t.append(arr[i])
					chk[i] = 2
				elif f == 1:
					one.append(arr[i])
					o.append(arr[i])
					chk[i] = 1
				else:
					two.append(arr[i])
					t.append(arr[i])
					chk[i] = 2
			one.sort()
			two.sort()
			if one == o and two == t:
				if len(one) == 0 or len(two) == 0:
					ans = 1
				elif one[-1] <= two[0]:
					ans = 1
			if ans == 1:
				print(*chk, sep='')
				break
		if ans == 0:
			print('-')
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		py2 = round(0.5)
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2 == 1:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def get_array():
	return list(map(int, sys.stdin.readline().split()))

def get_ints():
	return map(int, sys.stdin.readline().split())

def input():
	return sys.stdin.readline().strip()
main()


def handler_s(s):
	s = [(int(o), j) for (j, o) in enumerate(s)]
	s.sort(key=lambda x: x[0])
	n = len(s)
	f_old_p = -1
	t_old_p = -1
	min_t = 10
	result = [0] * n
	for (c, pos) in s:
		if pos > f_old_p and c <= min_t:
			result[pos] = '1'
			f_old_p = pos
		elif pos > t_old_p:
			result[pos] = '2'
			t_old_p = pos
			if min_t == 10:
				min_t = c
		else:
			result = []
			break
	if result:
		return ''.join(result)
	else:
		return '-'
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	print(handler_s(s))


for _ in range(int(input())):
	n = int(input())
	d = [*map(int, input())]
	s = d[:]
	s.sort()
	o = []
	i = 0
	ans = []
	for j in range(n):
		if d[j] == s[i]:
			ans.append('1')
			i += 1
		else:
			ans.append('2')
	t = []
	for i in range(n):
		if ans[i] == '1':
			t.append(d[i])
	for i in range(n):
		if ans[i] == '2':
			t.append(d[i])
	print(''.join(ans) if t == s else '-')


d = True

def debug(*args, **kwargs):
	if d:
		print(*args, **kwargs)

def get_result(numbers):
	for x in range(10):
		colors = [None] * len(numbers)
		group1 = []
		group2 = []
		col2_start = None
		for (i, number) in enumerate(numbers):
			if number < x:
				colors[i] = 1
			elif number > x:
				colors[i] = 2
				if col2_start is None:
					col2_start = i
		for (i, number) in enumerate(numbers):
			if number == x:
				if col2_start is not None and i < col2_start:
					colors[i] = 2
				else:
					colors[i] = 1
		for (i, number) in enumerate(numbers):
			if colors[i] == 1:
				group1.append(number)
			else:
				group2.append(number)
		if group1 == sorted(group1) and group2 == sorted(group2) and ((group2 == [] or group1 == []) or group2[0] >= group1[-1]):
			return colors
	raise ValueError
t = int(input())
for _ in range(t):
	l = int(input())
	numbers = [int(x) for x in input()]
	try:
		result = get_result(numbers)
		print(''.join([str(x) for x in result]))
	except ValueError:
		print('-')


t = int(input())
from collections import defaultdict
for _ in range(t):
	n = int(input())
	s = list(input())
	hash = defaultdict(list)
	for (i, j) in enumerate(s):
		hash[int(j)].append(i)
	la = []
	for i in s:
		la.append(int(i))
	la.sort()
	ba = -1
	for (j, i) in enumerate(s):
		if int(i) == int(la[-1]):
			ba = j
	yo = s.copy()
	poin = -2
	yo[ba] = 2
	for i in range(ba - 1, -1, -1):
		z = int(s[i])
		if z == la[poin]:
			poin -= 1
			yo[i] = 2
	s1 = []
	s2 = []
	for (j, i) in enumerate(yo):
		if yo[j] != 2:
			yo[j] = '1'
			s1.append(int(s[j]))
		else:
			yo[j] = '2'
			s2.append(int(s[j]))
	if s1 + s2 == la:
		print(''.join(yo))
	else:
		print('-')


t = int(input())
for i2 in range(t):
	n = int(input())
	s = str(input())
	(a, b, count) = ([], [], 0)
	for i in range(n):
		a.append(int(s[i]))
		b.append(int(s[i]))
	b.sort()
	(pointer, ans) = (0, [0] * n)
	for i in range(n):
		if a[i] == b[pointer]:
			pointer += 1
			ans[i] = 1
			count += 1
	for i in range(n):
		if pointer == n:
			break
		elif ans[i] == 1:
			pass
		elif a[i] == b[pointer]:
			pointer += 1
			ans[i] = 2
			count += 1
	if count < n:
		print('-')
	else:
		for i in ans:
			print(i, end='')
		print('')


def correct(a, b):
	f = 1
	for i in range(1, len(a)):
		if a[i] < a[i - 1]:
			f = 0
			break
	for i in range(1, len(b)):
		if b[i] < b[i - 1]:
			f = 0
			break
	if f == 0:
		return 0
	else:
		return 1
for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = [-1] * n
	for j in range(10):
		p1 = []
		p2 = []
		x = j
		g = 0
		f = 0
		for i in range(n):
			if int(s[i]) < x:
				ans[i] = '1'
				p1.append(int(s[i]))
			elif int(s[i]) > x:
				ans[i] = '2'
				p2.append(int(s[i]))
				f = 1
			elif f == 0:
				ans[i] = '2'
				p2.append(int(s[i]))
			else:
				ans[i] = '1'
				p1.append(int(s[i]))
		if correct(p1, p2):
			g = 1
			break
	if g == 0:
		print('-')
	else:
		print(''.join(ans))


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
start_time = time.time()

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]
T = int(input())
for _ in range(T):
	n = int(input())
	s = input()
	sort_s = ''
	d = {}
	for i in s:
		d[i] = d.get(i, 0) + 1
	for i in range(10):
		sort_s += str(i) * d.get(str(i), 0)
	j = 0
	ans = ['0'] * n
	c1 = ''
	c2 = ''
	for i in range(n):
		if s[i] == sort_s[j]:
			ans[i] = '1'
			j += 1
			c1 += s[i]
		else:
			ans[i] = '2'
			c2 += s[i]
	if c1 + c2 == ''.join(sort_s):
		print(''.join(ans))
	else:
		print('-')


import sys
import math
get_string = lambda : sys.stdin.readline().strip()
get_list = lambda : list(map(int, sys.stdin.readline().strip().split()))
get_int = lambda : int(sys.stdin.readline())
for _ in range(get_int()):
	n = get_int()
	s1 = get_string()
	s2 = ''.join(sorted(s1))
	i = 0
	j = 0
	count = 0
	used = [0 for i in range(n + 1)]
	while i < n and j < n:
		if s2[i] == s1[j]:
			i += 1
			count += 1
			used[j] = 1
			j += 1
		else:
			j += 1
	j = 0
	while i < n and j < n:
		if used[j] != 1 and s2[i] == s1[j]:
			i += 1
			count += 1
			used[j] = 2
			j += 1
		else:
			j += 1
	if count == n:
		for i in range(n):
			print(used[i], end='')
		print()
	else:
		print('-')


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input())]
	b = sorted(a)
	ans = []
	now = 0
	cek = []
	for i in range(0, n):
		if a[i] == b[now]:
			ans.append('1')
			now += 1
		else:
			ans.append('2')
	for i in range(0, n):
		if ans[i] == '1':
			cek.append(a[i])
	for i in range(0, n):
		if ans[i] == '2':
			cek.append(a[i])
	if cek == b:
		print(''.join(ans))
	else:
		print('-')


t = int(input())
while t:
	n = int(input())
	d = input()
	d = [d[i] for i in range(n)]
	ls = ['' for i in range(n)]
	i = n - 1
	mini = '9'
	while i >= 0:
		mini = min(mini, d[i])
		ls[i] = mini
		i -= 1
	color = [0 for i in range(n)]
	x = '9'
	for i in range(n):
		if d[i] <= ls[i] and d[i] <= x:
			color[i] = 1
		else:
			color[i] = 2
			x = min(x, d[i])
	ans = []
	for i in range(n):
		if color[i] == 1:
			ans.append(d[i])
	for i in range(n):
		if color[i] == 2:
			ans.append(d[i])
	d.sort()
	if ans == d:
		print(''.join((str(x) for x in color)))
	else:
		print('-')
	t -= 1


t = int(input())
for y in range(t):
	n = int(input())
	s = list(input())
	for i in range(n):
		s[i] = ord(s[i]) - ord('0')
	a = [0 for i in range(n)]
	l = sorted(s)
	ind = 0
	for i in range(n):
		if s[i] == l[ind]:
			ind += 1
			a[i] = 1
	for i in range(n):
		if ind >= n:
			break
		if s[i] == l[ind]:
			ind += 1
			a[i] = 2
	if len(set(a)) > 2:
		print('-')
	else:
		for i in range(n):
			print(a[i], end='')
	print()


from sys import setcheckinterval, stdin, setrecursionlimit
setcheckinterval(1000)
setrecursionlimit(10 ** 7)

def iin():
	return int(stdin.readline())

def lin():
	return list(map(int, stdin.readline().split()))
for _ in range(iin()):
	n = iin()
	a = list(map(int, list(input())))
	sa = [[j, i] for (i, j) in enumerate(a)]
	sa.sort()
	cc1 = []
	cc2 = []
	for (i, j) in sa:
		if cc1:
			if cc1[-1] < j:
				if cc2 and a[cc2[0]] < i:
					cc2.append(j)
				else:
					cc1.append(j)
			else:
				cc2.append(j)
		else:
			cc1.append(j)
	c1 = sorted(cc1)
	c2 = sorted(cc2)
	sol = [a[i] for i in c1] + [a[i] for i in c2]
	for i in range(1, n):
		if sol[i] < sol[i - 1]:
			print('-')
			break
	else:
		ans = [1 for i in range(n)]
		for i in c2:
			ans[i] = 2
		print(*ans, sep='')


for _ in range(int(input())):
	n = int(input())
	s = input()
	sort_s = ''.join(sorted(s))
	j = 0
	ans = ['0'] * n
	c1 = ''
	c2 = ''
	for i in range(n):
		if s[i] == sort_s[j]:
			ans[i] = '1'
			j += 1
			c1 += s[i]
		else:
			ans[i] = '2'
			c2 += s[i]
	if c1 + c2 == ''.join(sort_s):
		print(''.join(ans))
	else:
		print('-')


from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def powmod(a, b):
	a %= mod
	if a == 0:
		return 0
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % mod
		a = a * a % mod
		b >>= 1
	return res

def main():
	for _ in range(ii()):
		n = ii()
		s = si()
		a = []
		s = list(s)
		pos = ['0'] * n
		pos[n - 1] = s[n - 1]
		for i in range(n - 2, -1, -1):
			pos[i] = min(pos[i + 1], s[i])
		c1 = '0'
		f = 0
		c2 = '0'
		f1 = '-1'
		for i in range(n):
			if s[i] <= pos[i] and (f1 == '-1' or (f1 != '-1' and s[i] <= f1)):
				continue
			elif s[i] >= c1:
				if f1 == '-1':
					f1 = s[i]
				c1 = s[i]
				a.append(i)
			else:
				f = 1
				break
		if f == 1:
			print('-')
		else:
			ans = ['1'] * n
			for i in a:
				ans[i] = '2'
			print(''.join(ans))
main()


T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	D = list(map(int, list(input())))
	for middle in range(10):
		S = []
		one = -1
		two = -1
		for d in D:
			if d < middle:
				if one > d:
					break
				one = d
				S.append('1')
			elif d > middle:
				if two > d:
					break
				two = d
				S.append('2')
			elif two <= d:
				two = d
				S.append('2')
			else:
				one = d
				S.append('1')
		else:
			ans.append(''.join(S))
			break
	else:
		ans.append('-')
print(*ans, sep='\n')


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, list(input().strip())))
	ans = [0] * n
	arr = []
	for i in range(n):
		arr.append([s[i], i])
	arr.sort(key=lambda x: x[0])
	ans[arr[0][1]] = 1
	for i in range(1, n):
		if arr[i][1] > arr[i - 1][1]:
			ans[arr[i][1]] = 1
		else:
			break
	value = arr[i][0]
	ii = i
	j = 0
	for ii in range(i, n):
		if arr[ii][0] != value:
			break
		if arr[ii][1] > arr[i - 1][1]:
			ans[arr[ii][1]] = 1
		else:
			ans[arr[ii][1]] = 2
			j = arr[ii][1]
	for i in range(ii, n):
		if arr[i][1] >= j:
			j = arr[i][1]
			ans[arr[i][1]] = 2
		else:
			break
	else:
		print(''.join(map(str, ans)))
		continue
	print('-')


import sys
input = lambda : sys.stdin.readline().strip('\r\n')
for _ in range(int(input())):
	n = int(input())
	s = list((int(x) for x in input()))
	a = [0] * n
	l = sorted(s)
	ind = 0
	for i in range(n):
		if s[i] == l[ind]:
			ind += 1
			a[i] = 1
	for i in range(n):
		if ind >= n:
			break
		if s[i] == l[ind]:
			ind += 1
			a[i] = 2
	if len(set(a)) > 2:
		print('-')
	else:
		for i in range(n):
			print(a[i], end='')
	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):
			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)
			elif 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('-')


import sys
input = sys.stdin.readline

def getInt():
	return int(input())

def getVars():
	return map(int, input().split())

def getList():
	return list(map(int, input().split()))

def getStr():
	return input().strip()

def addDictList(d, key, val):
	if key not in d:
		d[key] = []
	d[key].append(val)

def addDictInt(d, key, val):
	if key not in d:
		d[key] = 0
	d[key] = val

def addDictCount(d, key):
	if key not in d:
		d[key] = 0
	d[key] += 1

def addDictSum(d, key, val):
	if key not in d:
		d[key] = 0
	d[key] += val
t = getInt()
for _ in range(t):
	n = getInt()
	s = getStr()
	res = ['0'] * n
	c = 1
	last = -1
	for ch in range(10):
		char = str(ch)
		p = s.find(char)
		if p > -1:
			if p < last:
				last1 = last
				c += 1
				if c > 2:
					res = '-'
					break
				while p > -1:
					if p < last1:
						res[p] = '2'
						last = p
					else:
						res[p] = '1'
					p = s.find(char, p + 1)
		while p > -1:
			last = p
			res[p] = str(c)
			p = s.find(char, p + 1)
	if res == '-':
		print(res)
	else:
		for i in range(n):
			print(res[i], end='')
		print()


a = int(input())
for i in range(a):
	b = int(input())
	c = input()
	suf = [0] * b
	c = c[::-1]
	ans = [0] * b
	suf[0] = int(c[0])
	for i in range(1, b):
		suf[i] = min(suf[i - 1], int(c[i]))
	suf.reverse()
	c = c[::-1]
	ma = 0
	mi = 10
	f = True
	for i in range(b):
		if int(c[i]) == suf[i] and int(c[i]) <= mi:
			ans[i] = 1
		else:
			if int(c[i]) < ma:
				print('-')
				f = False
				break
			ans[i] = 2
			ma = max(int(c[i]), ma)
			mi = min(int(c[i]), mi)
	if f:
		for x in ans:
			print(x, end='')
		print()


from copy import deepcopy
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, list(input())))
	narr = deepcopy(arr)
	narr.sort()
	color = [0] * n
	no = 1
	(i, j) = (0, 0)
	while i < n:
		while j < n:
			if i == n:
				break
			if arr[j] == narr[i] and color[j] == 0:
				color[j] = no
				i += 1
			j += 1
		no += 1
		if no == 3:
			break
		j = 0
	if 0 in color:
		print('-')
	else:
		print(''.join(list(map(str, color))))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = list(input())
	l = [0 for i in range(n)]
	small = 10
	for i in range(n - 1, -1, -1):
		small = min(small, int(s[i]))
		l[i] = small
	an = l2 = l1 = 0
	start = None
	for i in range(n):
		temp = int(s[i])
		if l[i] >= temp and l1 <= temp and (start == None or temp <= start):
			s[i] = 1
			l1 = temp
		elif l2 <= temp:
			s[i] = 2
			l2 = temp
			if start == None:
				start = temp
		else:
			an = 1
			break
	if an:
		print('-')
	else:
		print(''.join((str(e) for e in s[:-1])))


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, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	for _ in range(ri()):
		n = ri()
		a = list(rs())
		d = Counter(a)
		z = sorted(a)
		if z == a:
			print('1' * n)
		else:
			ind = {}
			for i in range(n):
				if a[i] in ind:
					ind[a[i]].append(i)
				else:
					ind[a[i]] = [i]
			s = '0123456789'
			ans = ['2'] * n
			prev = -1
			for i in range(10):
				if s[i] in d:
					k = ind[s[i]]
					if k[0] > prev:
						for j in k:
							ans[j] = '1'
							prev = j
					else:
						g = k[::-1]
						for j in g:
							if j > prev:
								ans[j] = '1'
						break
			z1 = []
			z2 = []
			for i in range(n):
				if ans[i] == '1':
					z1.append(a[i])
				else:
					z2.append(a[i])
			zn = z1 + z2
			if zn == z:
				print(''.join(ans))
			else:
				print('-')
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


import sys
import copy
from operator import itemgetter
tcs = int(input())
for _ in range(tcs):
	n = int(input())
	inp = list(map(int, list(sys.stdin.readline().rstrip())))
	ok = False
	for p in range(10):
		l1 = []
		l2 = []
		used = [0] * n
		bound = -1
		for i in range(n):
			if inp[i] < p:
				l1.append(i)
				used[i] = 1
		for i in range(n):
			if inp[i] > p and used[i] == 0:
				if bound == -1:
					bound = i
				l2.append(i)
				used[i] = 2
		for i in range(n):
			if inp[i] == p and i < bound and (used[i] == 0):
				l2.append(i)
				used[i] = 2
			if inp[i] == p and i > bound and (used[i] == 0):
				l1.append(i)
				used[i] = 1
		orig1 = []
		orig2 = []
		for i in range(n):
			if used[i] == 1:
				orig1.append(inp[i])
			else:
				orig2.append(inp[i])
		orig3 = orig1 + orig2
		if orig3 == sorted(orig3):
			for i in range(n):
				print(used[i], end='')
				ok = True
			print()
			break
	if not ok:
		print('-')


import sys
input = sys.stdin.readline
Q = int(input())
Query = []
for _ in range(Q):
	N = int(input())
	S = list(input().rstrip())
	Query.append((N, S))
for (N, S) in Query:
	ans = []
	for start in range(10):
		last = start
		last1 = -1
		T = []
		for (i, s) in enumerate(S):
			n = int(s)
			if n >= last:
				T.append('2')
				last = n
			elif n >= last1:
				T.append('1')
				last1 = n
			else:
				T = []
				break
		if T and last1 <= start:
			ans = T
	if not ans:
		print('-')
	else:
		print(''.join(ans))


cases = int(input())
for t in range(cases):
	n = int(input())
	d = list(map(int, list(input())))
	sd = sorted(d)
	for i in range(10):
		f = 0
		out = ['1'] * n
		for j in range(n):
			if d[j] < i:
				out[j] = '1'
			elif d[j] > i:
				out[j] = '2'
		fi2 = n
		if '2' in out:
			fi2 = out.index('2')
		for j in range(fi2):
			if d[j] == i:
				out[j] = '2'
		fn = [d[j] for j in range(n) if out[j] == '1'] + [d[j] for j in range(n) if out[j] == '2']
		for j in range(n):
			if fn[j] != sd[j]:
				f = 1
				break
		if f == 0:
			break
	if f == 0:
		print(''.join(out))
	else:
		print('-')


import sys
input = sys.stdin.readline
t = int(input())
for testcases in range(t):
	n = int(input())
	d = list(map(int, list(input().strip())))
	MIN = 10
	MAX = -1
	for i in range(1, n):
		if d[i] < d[i - 1]:
			MIN = min(MIN, d[i - 1])
			MAX = max(MAX, d[i])
	if MIN < MAX:
		print('-')
		continue
	elif MIN == 10:
		print('1' * n)
		continue
	for k in range(MAX, MIN + 1):
		ANS = [0] * n
		for i in range(n):
			if d[i] < k:
				ANS[i] = 1
			elif d[i] > k:
				ANS[i] = 2
		be = n
		if 2 in ANS:
			be = ANS.index(2)
		for i in range(n):
			if d[i] == k:
				if i < be:
					ANS[i] = 2
				else:
					ANS[i] = 1
		NOW1 = 0
		NOW2 = 0
		flag = 1
		for i in range(n):
			if ANS[i] == 1:
				if d[i] < NOW1:
					flag = 0
					break
				else:
					NOW1 = max(d[i], NOW1)
			elif d[i] < NOW2:
				flag = 0
				break
			else:
				NOW2 = max(d[i], NOW2)
			if flag == 0:
				break
		if flag == 1:
			print(''.join(map(str, ANS)))
			break
	else:
		print('-')


from sys import stdin, stdout
from math import gcd, sqrt, inf
from collections import deque
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(x)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 1 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
N = inf
for _ in range(I()):
	n = I()
	a = list(map(int, S()))
	v = [0] * n
	b = sorted(a)
	id = 0
	for i in range(n):
		if a[i] == b[id]:
			v[i] = 1
			id += 1
	lst = -1
	flg = True
	for i in range(n):
		if not v[i]:
			if a[i] < lst:
				flg = False
				break
			v[i] = 2
			lst = a[i]
	if flg:
		print(*v, sep='')
	else:
		print('-')


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in list(input())] + [-1]
	st = [n]
	m = [0] * n
	for i in range(n - 1, -1, -1):
		while a[st[-1]] >= a[i]:
			st.pop()
		m[i] = st[-1]
		st.append(i)
	prev = 0
	arr = [0] * n
	pr = 10
	for i in range(n):
		if m[i] == n and a[i] >= prev and (a[i] <= pr):
			arr[i] = 1
			prev = a[i]
		else:
			pr = min(pr, a[i])
	for i in range(n):
		if arr[i] != 1:
			if a[i] < prev:
				print('-')
				break
			else:
				arr[i] = 2
				prev = a[i]
	else:
		tot = ''
		for item in arr:
			tot += str(item)
		print(tot)


def is_sorted(l):
	return all((l[i - 1] <= l[i] for i in range(1, len(l))))

def coloring(nums, pivot):
	if len(nums) == 1:
		return '1'
	(res, a, b) = ('', [], [])
	for el in nums:
		if el < pivot:
			res += '1'
			if a and a[-1] > el:
				return '-'
			a.append(el)
		elif el > pivot:
			res += '2'
			if b and b[-1] > el:
				return '-'
			b.append(el)
		elif not b or (b and b[-1] == pivot):
			res += '2'
			b.append(el)
		elif not a or (a and a[-1] <= pivot):
			res += '1'
			a.append(el)
		else:
			return '-'
	return res

def coloring2(nums):
	for i in [5, 4, 6, 3, 7, 2, 8, 1, 9, 0]:
		r = coloring(nums, i)
		if r != '-':
			return r
	return '-'
t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, list(input())))
	print(coloring2(nums))


from sys import stdin, stdout
import heapq
import cProfile, math
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)
fac_warm_up = False
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n
		self.lista = [[_] for _ in range(n)]

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]
		self.lista[a] += self.lista[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def prime_factors(n):
	factors = dict()
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n // i
	if n > 2:
		factors[n] = 1
	return factors

def all_factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def fibonacci_modP(n, MOD):
	if n < 2:
		return 1
	return (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n, p):
	if p <= n:
		return 0
	res = p - 1
	for i in range(n + 1, p):
		res = res * cached_fn(InverseEuler, i, p) % p
	return res

def binary(n, digits=20):
	b = bin(n)[2:]
	b = '0' * (digits - len(b)) + b
	return b

def is_prime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

def generate_primes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	return prime
factorial_modP = []

def warm_up_fac(MOD):
	global factorial_modP, fac_warm_up
	if fac_warm_up:
		return
	factorial_modP = [1 for _ in range(fac_warm_up_size + 1)]
	for i in range(2, fac_warm_up_size):
		factorial_modP[i] = factorial_modP[i - 1] * i % MOD
	fac_warm_up = True

def InverseEuler(n, MOD):
	return pow(n, MOD - 2, MOD)

def nCr(n, r, MOD):
	global fac_warm_up, factorial_modP
	if not fac_warm_up:
		warm_up_fac(MOD)
		fac_warm_up = True
	return factorial_modP[n] * (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD) % MOD) % MOD

def test_print(*args):
	if testingMode:
		print(args)

def display_list(list1, sep=' '):
	stdout.write(sep.join(map(str, list1)) + '\n')

def display_2D_list(li):
	for i in li:
		print(i)

def prefix_sum(li):
	sm = 0
	res = []
	for i in li:
		sm += i
		res.append(sm)
	return res

def get_int():
	return int(stdin.readline().strip())

def get_tuple():
	return map(int, stdin.readline().split())

def get_list():
	return list(map(int, stdin.readline().split()))
memory = dict()

def clear_cache():
	global memory
	memory = dict()

def cached_fn(fn, *args):
	global memory
	if args in memory:
		return memory[args]
	else:
		result = fn(*args)
		memory[args] = result
		return result

def ncr(n, r):
	return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))

def binary_search(i, li):
	fn = lambda x: li[x] - x // i
	x = -1
	b = len(li)
	while b >= 1:
		while b + x < len(li) and fn(b + x) > 0:
			x += b
		b = b // 2
	return x
TestCases = True
fac_warm_up_size = 10 ** 5 + 100
optimise_for_recursion = False

def main():
	n = get_int()
	li = list(map(int, list(stdin.readline().strip())))
	a_prev = -1
	b_prev = -1
	minis = [li[-1] for _ in range(n + 1)]
	for index in range(n - 2, -1, -1):
		minis[index] = min(li[index + 1], minis[index + 1])
	res = [1 for _ in range(n)]
	b1 = 10 ** 10
	for (i, ele) in enumerate(li):
		if ele > minis[i]:
			if ele >= b_prev:
				res[i] = 2
				if b_prev == -1:
					b1 = ele
				b_prev = ele
			else:
				print('-')
				return
		elif ele >= a_prev and b1 >= ele:
			a_prev = ele
		elif ele >= b_prev:
			res[i] = 2
			if b_prev == -1:
				b1 = ele
			b_prev = ele
		else:
			print('-')
			return
	if a_prev > b1:
		print('-')
		return
	display_list(res, '')
if TestCases:
	for i in range(get_int()):
		main()
else:
	main() if not optimise_for_recursion else threading.Thread(target=main).start()


import math
for _ in range(int(input())):
	n = int(input())
	s = input()
	b = [0] * 11
	a = [0] * (n + 10)
	j = 0
	flag = True
	for i in range(n):
		b[int(s[i])] += 1
	for i in range(n):
		while b[j] == 0 and j < 10:
			j += 1
		if int(s[i]) == j and b[j] > 0:
			b[j] -= 1
			a[i] = 1
	for i in range(n):
		while b[j] == 0 and j < 10:
			j += 1
		if int(s[i]) == j and b[j] > 0:
			b[j] -= 1
			a[i] = 2
	for i in range(n):
		if a[i] == 0:
			print('-')
			flag = False
			break
	if flag:
		for i in range(n):
			print(a[i], end='')
		print()


import sys, math
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	s = list(input())
	freq = [0] * 10
	for i in range(n):
		freq[int(s[i])] += 1
	ans = ''
	f1 = [0] * 10
	quit = 0
	f2 = [0] * 10
	for i in range(n):
		flag = True
		for j in range(int(s[i])):
			if freq[j] > 0:
				flag = False
				break
		if flag:
			f = False
			ff = False
			for j in range(int(s[i])):
				if f2[j] > 0:
					f = True
			for j in range(int(s[i]) + 1, 10):
				if f2[j] > 0:
					ff = True
			if f and ff:
				print('-')
				quit = -1
				break
			elif f:
				ans += '2'
			else:
				ans += '1'
		else:
			flag = True
			for j in range(int(s[i]) + 1, 10):
				if f1[j] > 0:
					flag = False
			if flag:
				ans += '2'
				f2[int(s[i])] += 1
			else:
				print('-')
				quit = -1
				break
		f1[int(s[i])] += 1
		freq[int(s[i])] -= 1
	if quit == 0:
		print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def pre(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j and s[i] != s[j]:
			j = pi[j - 1]
		if s[i] == s[j]:
			j += 1
		pi[i] = j
	return pi

def prod(a):
	ans = 1
	for each in a:
		ans = ans * each
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)
from math import inf
from collections import deque

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if True else 1):
	n = int(input())
	s = input()
	total = 0
	a = [0] * 10
	ans = [0] * n
	for i in s:
		a[int(i)] += 1
	cur = 0
	for i in range(n):
		while cur <= 9 and a[cur] == 0:
			cur += 1
		if cur == 10:
			break
		if int(s[i]) == cur:
			ans[i] = 1
			a[cur] -= 1
			total += 1
			while cur <= 9 and a[cur] == 0:
				cur += 1
			if cur == 10:
				break
	if total != n:
		for i in range(n):
			while cur <= 9 and a[cur] == 0:
				cur += 1
			if cur == 10:
				break
			if int(s[i]) == cur:
				ans[i] = 2
				a[cur] -= 1
				total += 1
				while cur <= 9 and a[cur] == 0:
					cur += 1
				if cur == 10:
					break
	if total != n:
		print('-')
	else:
		print(''.join((str(k) for k in ans)))


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(''.join([str(x) for x in arr]))
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input()]
	possible = False
	colouring = [0 for _ in range(n)]
	for twoLowerLimit in range(10):
		one = -float('inf')
		two = -float('inf')
		ok = True
		for i in range(n):
			x = arr[i]
			if x > twoLowerLimit:
				if x < two:
					ok = False
					break
				colouring[i] = 2
				two = x
			elif x < twoLowerLimit:
				if x < one:
					ok = False
					break
				colouring[i] = 1
				one = x
			elif x >= two:
				colouring[i] = 2
				two = x
			else:
				colouring[i] = 1
				one = x
		if ok:
			possible = True
			break
	if possible:
		oneLineArrayPrint(colouring)
	else:
		print('-')


import sys

class CPaintTheDigits:

	def solve(self):
		t = int(input())
		for _ in range(t):
			n = int(input())
			d = [int(_) for _ in list(input().strip())]
			for dg in range(1, 11):
				cur = []
				ok = True
				for i in range(n):
					if cur and d[i] < d[cur[-1]]:
						ok = False
					if d[i] < dg:
						cur.append(i)
				if not ok:
					continue
				if cur:
					s = cur[-1] if cur else -1
					for i in range(s + 1, n):
						if d[i] == dg:
							cur.append(i)
				ans = [2] * n
				for i in cur:
					ans[i] = 1
				res_d = [d[i] for i in range(n) if ans[i] == 1]
				res_d += [d[i] for i in range(n) if ans[i] == 2]
				if res_d == sorted(res_d):
					print(''.join((str(col) for col in ans)))
					break
			else:
				print('-')
solver = CPaintTheDigits()
input = sys.stdin.readline
solver.solve()


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def A():
	n = I()
	a = LI()
	a.sort()
	f = [1] * n
	p = 0
	ans = 0
	while p < n:
		while p < n and (not f[p]):
			p += 1
		if p == n:
			break
		ans += 1
		for i in range(n):
			if a[i] % a[p] == 0:
				f[i] = 0
	print(ans)
	return

def B():
	n = I()
	s = list(map(int, input()))
	g = LIR(n)
	ans = sum(s)
	for t in range(30000):
		for i in range(n):
			(ai, bi) = g[i]
			if t < bi:
				continue
			if (t - bi) % ai == 0:
				s[i] ^= 1
		su = sum(s)
		if ans < su:
			ans = su
	print(ans)
	return

def C():
	t = I()
	for _ in range(t):
		n = I()
		s = list(map(int, input()))
		mi = [s[n - 1]]
		for i in range(n - 1)[::-1]:
			mi.append(min(mi[-1], s[i]))
		mi = mi[::-1]
		ma = [s[0]]
		for i in range(1, n):
			ma.append(max(ma[-1], s[i]))
		ans = [None] * n
		j = n - 1
		while j >= 0 and ma[j] == s[j]:
			ans[j] = 2
			j -= 1
		if j == -1:
			print(*ans, sep='')
			continue
		for i in range(n):
			if ans[i] == None:
				if mi[i] == s[i]:
					ans[i] = 1
				else:
					ans[i] = 2
		q = [s[i] for i in range(n) if ans[i] > 1]
		p = [q[i] for i in range(len(q))]
		p.sort()
		if not p:
			print(*ans, sep='')
		elif p == q and s[j] <= p[0]:
			print(*ans, sep='')
		else:
			print('-')
	return

def D():

	def root(x):
		if x == par[x]:
			return x
		par[x] = root(par[x])
		return par[x]

	def unite(x, y):
		x = root(x)
		y = root(y)
		if rank[x] < rank[y]:
			par[x] = y
		else:
			par[y] = x
			if rank[x] == rank[y]:
				rank[x] += 1
	(n, k) = LI()
	par = [i for i in range(n)]
	rank = [0] * n
	for i in range(k):
		(x, y) = LI()
		x -= 1
		y -= 1
		if root(x) != root(y):
			unite(x, y)
	size = [0] * n
	for i in range(n):
		size[root(i)] += 1
	ans = 0
	for i in size:
		if i > 0:
			ans += i - 1
	print(k - ans)
	return

def E():
	t = I()
	for _ in range(t):
		(n, m) = LI()
		s = LIR(n)
		s = [[s[i][j] for i in range(n)] for j in range(m)]
		if n <= m:
			ma = [max(s[i]) for i in range(m)]
			ma.sort(reverse=True)
			print(sum(ma[:n]))
		else:
			ans = 0
			k = [[]]
			for _ in range(m):
				k_ = []
				for i in range(n):
					k_ += [x + [i] for x in k]
				k = [x for x in k_]
			for l in k:
				s_ = [[s[i][(j + l[i]) % n] for j in range(n)] for i in range(m)]
				print(l)
				p = sum([max([s_[i][j] for i in range(m)]) for j in range(n)])
				print(s_, p)
				if ans < p:
					ans = p
			print(ans)
	return

def F():
	return

def G():

	def root(x):
		if x == par[x]:
			return x
		par[x] = root(par[x])
		return par[x]

	def unite(x, y):
		x = root(x)
		y = root(y)
		if rank[x] < rank[y]:
			par[x] = y
		else:
			par[y] = x
			if rank[x] == rank[y]:
				rank[x] += 1
	m = 200000
	par = [i for i in range(m)]
	rank = [0] * m
	(n, q) = LI()
	a = LI()
	for i in range(n):
		a[i] -= 1
	count = defaultdict(lambda : 0)
	l = defaultdict(lambda : 0)
	lis = []
	for i in range(n):
		ai = a[i]
		if count[ai] == 0:
			l[ai] = i
			lis.append(ai)
		count[ai] += 1
	f = defaultdict(lambda : 0)
	r = defaultdict(lambda : 0)
	for i in range(n)[::-1]:
		ai = a[i]
		if not f[ai]:
			r[ai] = i
			f[ai] = 1
	f = [0] * n
	for i in lis:
		(li, ri) = (l[i], r[i])
		f[li] += 1
		f[ri] -= 1
	for i in range(n - 1):
		if f[i] > 0:
			(x, y) = (a[i], a[i + 1])
			if root(x) != root(y):
				unite(x, y)
		f[i + 1] += f[i]
	size = defaultdict(lambda : [])
	for i in l:
		size[root(i)].append(count[i])
	ans = 0
	for i in size.values():
		ans += sum(i) - max(i)
	print(ans)
	return

def H():
	return
C()


def oneLineArrayPrint(arr):
	print(''.join([str(x) for x in arr]))
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inf = float('inf')
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input()]
	col = [0 for _ in range(n)]
	p = True
	for i in range(n - 1):
		if arr[i] > arr[i + 1]:
			if col[i] == 1:
				p = False
				break
			col[i] = 2
			col[i + 1] = 1
	nr1 = [inf for _ in range(n)]
	for i in range(n - 1, 0, -1):
		nr1[i - 1] = nr1[i]
		if col[i] == 1:
			nr1[i - 1] = min(arr[i], arr[i - 1])
	min2 = inf
	for i in range(n):
		if col[i] == 0:
			if arr[i] <= nr1[i] and arr[i] <= min2:
				col[i] = 1
			else:
				col[i] = 2
		if col[i] == 2:
			min2 = min(min2, arr[i])
	min1 = -inf
	min2 = -inf
	max1 = -inf
	minn2 = inf
	for i in range(n):
		if col[i] == 1:
			if arr[i] < min1:
				p = False
				break
			min1 = arr[i]
			max1 = max(max1, arr[i])
		elif col[i] == 2:
			if arr[i] < min2:
				p = False
				break
			min2 = arr[i]
			minn2 = min(minn2, arr[i])
	if minn2 < max1:
		p = False
	if p:
		oneLineArrayPrint(col)
	else:
		print('-')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
for i in range(n):
	l = int(input())
	s = list(input())
	d = dict()
	for j in range(l):
		if int(s[j]) in d:
			d[int(s[j])].append(int(j))
		else:
			d.update({int(s[j]): [int(j)]})
	color1 = []
	color2 = []
	prev = -1
	last = 10
	for k in range(0, 10):
		if k not in d.keys():
			continue
		for j in range(len(d[k])):
			if d[k][j] > prev and k <= last:
				color1.append(d[k][j])
				prev = d[k][j]
				d[k][j] = -2
			else:
				last = min(k, last)
	prev = -1
	for k in range(0, 10):
		if k not in d.keys():
			continue
		for j in range(len(d[k])):
			if d[k][j] > prev:
				color2.append(d[k][j])
				prev = d[k][j]
				d[k][j] = -2
	ans = [0] * l
	for j in color1:
		ans[j] = 1
	for j in color2:
		ans[j] = 2
	if min(ans) == 0:
		print('-')
	else:
		print(*ans, sep='')


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())

def ans(l, n, a, b):
	i = 1
	a = l[0]
	b = 0
	while i < n:
		while l[i] - l[i - 1] >= 0 and i < n:
			i += 1
		else:
			return -1

def inc(l, n):
	for i in range(1, n):
		if l[i] - l[i - 1] >= 0:
			continue
		else:
			return -1
	return 1

def dec(l, n):
	for i in range(1, n):
		if l[i] - l[i - 1] <= 0:
			continue
		else:
			return -1
	return 1

def solve(l, n, i):
	a = 0
	b = 0
	aa = [0] * n
	temp = 0
	for j in range(n):
		if l[j] < i:
			aa[j] = 1
			if l[j] >= a:
				a = l[j]
			else:
				return -1
		elif l[j] > i:
			aa[j] = 2
			if l[j] >= b:
				temp = 1
				b = l[j]
			else:
				return -1
		elif temp != 0:
			aa[j] = 1
			if l[j] >= a:
				a = l[j]
			else:
				return -1
		else:
			aa[j] = 2
			if l[j] >= b:
				b = l[j]
			else:
				return -1
	return aa
q = int(input())
for _ in range(q):
	n = int(input())
	l = list(input())
	s = 0
	for i in range(n):
		l[i] = int(l[i])
	for i in range(0, 10):
		if solve(l, n, i) == -1:
			continue
		else:
			s = 1
			kk = solve(l, n, i)
			for j in kk:
				print(j, end='')
			print('')
			break
	if s == 0:
		print('-')


T = int(input())
for test in range(T):
	n = int(input())
	arr = list(str(input()))
	mapp = []
	for (i, el) in enumerate(arr):
		mapp.append([int(el), i])
	sorted_map = sorted(mapp, key=lambda el: el[0])
	rr = [0] * len(sorted_map)
	base = sorted_map[0]
	rr[base[1]] = 1
	last = 100000
	for i in range(1, len(sorted_map)):
		if sorted_map[i][0] >= base[0] and sorted_map[i][1] > base[1] and (sorted_map[i][0] <= last):
			rr[sorted_map[i][1]] = 1
			base = sorted_map[i]
		else:
			rr[sorted_map[i][1]] = 2
			last = min(last, sorted_map[i][0])
	ok = True
	r1 = []
	r2 = []
	for i in range(len(rr)):
		if rr[i] == 1:
			r1.append(int(arr[i]))
		else:
			r2.append(int(arr[i]))
	r1.extend(r2)
	for i in range(1, len(r1)):
		if r1[i - 1] > r1[i]:
			ok = False
	if ok:
		rr = list(map(str, rr))
		print(''.join(rr))
	else:
		print('-')


q = int(input())
for rwr in range(q):
	n = int(input())
	ss = input()
	s = [int(ss[i]) for i in range(n)]
	dasie = 0
	maks = [0] * n
	maks[n - 1] = s[n - 1]
	for i in range(1, n):
		j = n - 1 - i
		maks[j] = min(maks[j + 1], s[j])
	ok = 0
	for t in range(1, 10):
		a = [s[i] for i in range(n) if s[i] <= t and (i == n - 1 or maks[i + 1] >= s[i])]
		b = [s[i] for i in range(n) if not (s[i] <= t and (i == n - 1 or maks[i + 1] >= s[i]))]
		chuj = 0
		for j in range(1, len(a)):
			if a[j] < a[j - 1]:
				chuj = 1
				break
		for j in range(1, len(b)):
			if b[j] < b[j - 1]:
				chuj = 1
				break
		if chuj == 0:
			c = a + b
			pup = 0
			for i in range(1, len(c)):
				if c[i] < c[i - 1]:
					pup = 1
					break
			if pup == 1:
				continue
			odp = [1 if s[k] <= t and (k == n - 1 or maks[k + 1] >= s[k]) else 2 for k in range(n)]
			ok = 1
			for i in range(len(odp)):
				if i < len(odp) - 1:
					print(odp[i], end='')
				else:
					print(odp[i])
			break
	if ok == 0:
		print('-')


for _ in range(int(input())):
	n = int(input())
	d = list(map(int, list(input())))
	a = [(d[i], i) for i in range(n)]
	a.sort()
	possible = True
	i1 = a[0][1]
	i2 = 0
	idx1 = [i1]
	idx2 = []
	min2 = a[n - 1][0]
	for i in range(1, n):
		if a[i][1] > i1 and a[i][0] <= min2:
			i1 = a[i][1]
			idx1.append(a[i][1])
		else:
			if a[i][1] < i2:
				possible = False
				break
			i2 = a[i][1]
			idx2.append(a[i][1])
			min2 = d[idx2[0]]
	if possible:
		colors = ['1' for i in range(n)]
		for i in idx2:
			colors[i] = '2'
		print(''.join(colors))
	else:
		print('-')


from random import randint
for _ in range(int(input())):
	n = int(input())
	D = list(map(int, list(input())))
	color = [2] * n
	mins = [-1] * (n - 1) + [D[-1]]
	for i in range(n - 2, -1, -1):
		mins[i] = min(D[i], mins[i + 1])
	minid = 0
	for i in range(n):
		if D[i] < D[minid]:
			minid = i
	last1 = minid
	first2 = 0 if minid != 0 else -1
	for i in range(minid, n - 1):
		if D[i] <= mins[i + 1] and (D[i] <= D[first2] or first2 == -1):
			color[i] = 1
			last1 = i
		elif first2 == -1:
			first2 = i
	j = 0
	while color[j] == 1:
		j += 1
	if D[j] >= D[-1]:
		color[-1] = 1
	if D[j] < D[last1]:
		print('-')
		continue
	prev = D[j]
	fl = True
	for i in range(j + 1, n):
		if color[i] == 2:
			if D[i] < prev:
				fl = False
				print('-')
				break
			prev = D[i]
	if fl:
		print(''.join(list(map(str, color))))


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('-')


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().strip().split(' '))

def li():
	return list(mi())

def dmain():
	sys.setrecursionlimit(100000000)
	threading.stack_size(40960000)
	thread = threading.Thread(target=main)
	thread.start()
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[0]

def sort2(l):
	return sorted(l, key=getKey)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def main():
	for _ in range(ii()):
		n = ii()
		s = si()
		arr = []
		for i in range(n):
			arr.append(int(s[i]))
		a = arr[:]
		a.sort()
		pos = 0
		f = [0] * n
		for i in range(n):
			if arr[i] == a[pos]:
				pos += 1
				f[i] = 1
		for i in range(n):
			if f[i] == 0:
				if arr[i] == a[pos]:
					pos += 1
					f[i] = 2
		if f.count(0) > 0:
			print('-')
		else:
			s = ''
			for i in range(n):
				s += str(f[i])
			print(s)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for k in range(t):
	n = int(input())
	d = [int(i) for i in input()]
	s = sorted(d)
	o = []
	l = 0
	ans = []
	for j in range(n):
		if d[j] == s[l]:
			ans.append('1')
			l += 1
		else:
			ans.append('2')
	t = []
	for i in range(n):
		if ans[i] == '1':
			t.append(d[i])
	for i in range(n):
		if ans[i] == '2':
			t.append(d[i])
	if t == s:
		print(''.join(ans))
	else:
		print('-')


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		n = int(input())
		s = list(map(int, list(input())))
		curidx = 0
		a = sorted(s)
		ans = [0 for x in range(n)]
		for x in range(n):
			if s[x] == a[curidx]:
				ans[x] = 1
				curidx += 1
		for x in range(n):
			if curidx == n:
				break
			if s[x] == a[curidx]:
				ans[x] = 2
				curidx += 1
				if curidx == n:
					break
		if curidx == n:
			print(*ans, sep='')
		else:
			print('-')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin
data = stdin.read().splitlines()[2::2]
for (i, s) in enumerate(data):
	(l, r) = (sorted(s, reverse=True), [''] * len(s))
	for (j, c) in enumerate(s):
		if c == l[-1]:
			del l[-1]
			r[j] = '1'
	for (j, c, f) in zip(range(999999), s, r):
		if not f and c == l[-1]:
			del l[-1]
			r[j] = '2'
	data[i] = ''.join(r) if all(r) else '-'
print('\n'.join(data))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for j in range(int(input())):
	n = int(input())
	vals = [int(k) for k in input()]
	ind = 0
	minny = min(vals)
	for s in range(n):
		if vals[s] > minny:
			ind = s
			break
	two = [ind]
	setty = set([ind])
	maxind = ind
	for s in range(n):
		if vals[s] >= vals[two[-1]] and maxind < s:
			two.append(s)
			setty.add(s)
			maxind = s
	one = []
	ones = set([])
	max1 = 0
	for s in range(n):
		if not s in setty:
			one.append(s)
			ones.add(s)
			max1 = max(max1, vals[s])
	for s in two:
		if vals[s] < max1:
			one.append(s)
			ones.add(s)
	one.sort()
	check = True
	checker = [vals[s] for s in one] + [vals[s] for s in range(n) if not s in ones]
	for s in range(1, n):
		if checker[s - 1] > checker[s]:
			check = False
			break
	if check == True:
		ans = ['' for s in range(n)]
		for s in range(n):
			if s in ones:
				ans[s] = '1'
			else:
				ans[s] = '2'
		print(''.join(ans))
	else:
		print('-')


for _ in range(int(input())):
	N = int(input())
	S = [int(i) for i in list(input())]
	s = sorted(S)[::-1]
	finalAr = []
	color = [0] * N
	for i in range(N):
		if s[-1] == S[i]:
			s.pop()
			color[i] = 1
			finalAr.append(S[i])
	for i in range(N):
		if color[i] == 0:
			color[i] = 2
			finalAr.append(S[i])
	if sorted(finalAr) == finalAr:
		for i in color:
			print(i, end='')
		print()
	else:
		print('-')


mod = 10 ** 9 + 7
from sys import stdin, stdout
import bisect
from bisect import bisect_left as bl
from bisect import bisect_right as br
import itertools
import collections
import math
import heapq
from random import randint as rn

def modinv(n, p):
	return pow(n, p - 2, p)

def ncr(n, r, p):
	t = fact[n] * (ifact[r] * ifact[n - r] % p) % p
	return t

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return map(int, input().split())

def GCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		ss = sin()
		s = []
		for i in range(n):
			s.append(int(ss[i]))
		p = [-1]
		q = []
		r = []
		ch = 0
		for i in s:
			if i >= p[-1]:
				if len(q) != 0 and i >= q[-1]:
					q.append(i)
					r.append(2)
					continue
				if len(q) > 0:
					if i > q[0]:
						ch = 1
						break
				p.append(i)
				r.append(1)
			else:
				new = []
				neww = []
				while i < p[-1]:
					k = p.pop()
					new.append(k)
					neww.append(2)
					r.pop()
				if len(q) == 0 or k >= q[-1]:
					new = new[::-1]
					q.extend(new)
					r.extend(neww)
				else:
					ch = 1
					break
				p.append(i)
				r.append(1)
		if ch == 0:
			print(*r, sep='')
		else:
			print('-')
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, list(input())))
	temp = [0] * n
	possible = True
	for x in range(10):
		possible = True
		idx = -1
		d = []
		for j in range(n):
			if a[j] < x:
				temp[j] = 1
			elif a[j] > x:
				temp[j] = 2
				if idx == -1:
					idx = j
			elif idx == -1:
				temp[j] = 2
			else:
				temp[j] = 1
			d.append([temp[j], a[j]])
		d.sort(key=lambda y: y[0])
		for j in range(n - 1):
			if d[j][1] > d[j + 1][1]:
				possible = False
				break
		if possible:
			print(''.join(map(str, temp)))
			break
	if not possible:
		print('-')


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	color = [0] * n
	for i in range(10):
		(prev_1, prev_2) = (-1, -1)
		for j in range(n):
			m = int(s[j])
			if i == m:
				if prev_2 <= m:
					prev_2 = m
					color[j] = 2
				elif prev_1 <= m:
					prev_1 = m
					color[j] = 1
				else:
					break
			elif i > m:
				if prev_1 <= m:
					prev_1 = m
					color[j] = 1
				else:
					break
			elif prev_2 <= m:
				prev_2 = m
				color[j] = 2
			else:
				break
		else:
			print(''.join(map(str, color)))
			break
	else:
		print('-')


t = int(input())

def najdi_podpostupnost(n, d):
	mensie = []
	indexy_mensich = []
	vacsie = []
	vystup = n * [None]
	for j in range(n - 1):
		if d[j + 1] - d[j] < 0:
			mensie.append(d[j + 1])
			indexy_mensich.append(j + 1)
			vystup[j + 1] = 1
			if len(mensie) > 1 and mensie[-1] < mensie[-2]:
				return '-'
	if len(mensie) < 1:
		return n * [1]
	for j in range(indexy_mensich[0]):
		if d[j] <= mensie[0]:
			vystup[j] = 1
		else:
			vystup[j] = 2
			vacsie.append(d[j])
	for j in range(len(mensie) - 1):
		for k in range(indexy_mensich[j] + 1, indexy_mensich[j + 1]):
			if d[k] > d[indexy_mensich[j + 1]]:
				vacsie.append(d[k])
				vystup[k] = 2
				if vacsie[-1] < vacsie[-2]:
					return '-'
			else:
				vystup[k] = 1
	for j in range(indexy_mensich[-1], n):
		if d[j] >= vacsie[-1]:
			vystup[j] = 2
		else:
			vystup[j] = 1
			mensie.append(d[j])
	if mensie[-1] <= vacsie[0]:
		return vystup
	else:
		return '-'
for i in range(t):
	n = int(input())
	d = [int(x) for x in list(input())]
	v = najdi_podpostupnost(n, d)
	if v == '_':
		print(v)
	else:
		print(''.join([str(x) for x in v]))


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)
		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')


t = int(input())
for _ in range(t):
	n = int(input())
	d = list(input())
	d = [int(i) for i in d]
	if n >= 2:
		for p in range(10):
			for q in range(p + 1, 10):
				flag = 1
				a = []
				b = []
				an = p
				bn = q
				b0 = bn
				for i in range(n):
					if bn <= d[i]:
						b.append(i)
						bn = d[i]
					elif an <= d[i] <= b0:
						a.append(i)
						an = d[i]
					else:
						flag = 0
						break
				if flag == 0:
					continue
				else:
					break
			if flag == 1:
				break
		if flag == 0:
			print('-')
		else:
			ans = [1] * n
			for i in b:
				ans[i] = 2
			print(''.join(map(str, ans)))
	else:
		print(1)


import sys
t = int(input())
for i in range(0, t):
	n = int(sys.stdin.readline().rstrip())
	s = list(sys.stdin.readline().rstrip())
	s = [[int(s[i]), i] for i in range(0, len(s))]
	s = sorted(s)
	l = 0
	m = s[0][1]
	mi = 0
	rm = 0
	pt = [0] * n
	rfi = False
	rft = False
	val = True
	pt[s[0][1]] = 1
	for j in range(1, len(s)):
		if s[j][0] != s[j - 1][0]:
			l = j
			if rfi:
				rft = True
		if s[j][1] >= m and (not rft):
			if mi == j - 1 or mi >= l:
				mi = j
				m = s[j][1]
			pt[s[j][1]] = 1
		else:
			rfi = True
			pt[s[j][1]] = 2
			if s[j][1] >= rm:
				rm = s[j][1]
			else:
				val = False
	if val:
		print(''.join([str(j) for j in pt]))
	else:
		print('-')


def find(A):
	for min_2 in range(10):
		ans_1 = []
		ans_2 = []
		cur_1 = -1
		cur_2 = -1
		flag = 1
		for i in range(len(A)):
			val = int(A[i])
			if val > min_2:
				ans_2 += [i]
				if len(ans_2) >= 2:
					if int(A[ans_2[-2]]) > int(A[ans_2[-1]]):
						flag = 0
						break
			elif val < min_2:
				ans_1 += [i]
				if len(ans_1) >= 2:
					if int(A[ans_1[-2]]) > int(A[ans_1[-1]]):
						flag = 0
						break
			elif ans_2:
				if int(A[ans_2[-1]]) == min_2:
					ans_2 += [i]
				else:
					ans_1 += [i]
			else:
				ans_2 += [i]
		if flag == 1:
			dp = ['1'] * len(A)
			for x in ans_2:
				dp[x] = '2'
			return ''.join(dp)
	return '-'
for _ in range(int(input())):
	_ = input()
	s = input()
	print(find(s))


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('-')
main()


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
input = lambda : sys.stdin.readline().strip()
t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, list(input())))
	ind = list(range(n))
	ind.sort(key=lambda x: 100000 * s[x] + x)
	if ind == list(range(n)):
		print('1' * n)
	else:
		color = []
		for i in range(n):
			color.append('0')
		I = -1
		last = -1
		for i in ind:
			if (last == -1 or i > last) and (I == -1 or s[i] <= s[I]):
				color[i] = '1'
				last = i
			if I == -1 and color[i] == '0':
				I = i
		for i in range(n):
			if color[i] == '0':
				color[i] = '2'
		check = []
		for i in range(n):
			if color[i] == '1':
				check.append(s[i])
		for i in range(n):
			if color[i] == '2':
				check.append(s[i])
		for i in range(1, n):
			if check[i] < check[i - 1]:
				print('-')
				break
		else:
			print(''.join(color))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	visited = set()
	for i in range(11):
		visited.add(i)
		f = 0
		ma = -1
		v1 = set()
		for j in range(i + 1):
			for k in range(n):
				if int(s[k]) == j:
					if k < ma:
						f = 1
						break
					else:
						v1.add(k)
						ma = max(ma, k)
			if f:
				break
		for k in range(ma + 1, n):
			if int(s[k]) == i + 1:
				v1.add(k)
		if f:
			continue
		ma = -1
		v2 = set()
		for j in range(i + 1, 11):
			for k in range(n):
				if int(s[k]) == j and k not in v1:
					if k < ma:
						f = 1
						break
					else:
						v2.add(k)
						ma = max(ma, k)
			if f:
				break
		if not f:
			break
	if f:
		print('-')
		continue
	ans = ['2'] * n
	for i in v1:
		ans[i] = '1'
	print(''.join(ans))


elem = int(input())
for x in range(elem):
	num = int(input())
	temp = str(input())
	point = 0
	check = 0
	firstList = []
	secondList = []
	tempSeq = []
	for i in range(len(temp)):
		if i > 0:
			if int(temp[i]) < int(temp[i - 1]) and check == 0:
				tempList = []
				qwe = 0
				for val in firstList:
					if val > int(temp[i]):
						secondList.append(val)
						qwe = qwe + 1
						del tempSeq[-1]
					else:
						tempList.append(val)
				for qw in range(qwe):
					tempSeq.append(2)
				tempSeq.append(1)
				tempList.append(int(temp[i]))
				firstList = tempList.copy()
				check = 1
			else:
				if check == 0:
					if int(temp[i]) >= firstList[-1]:
						firstList.append(int(temp[i]))
						tempSeq.append(1)
					elif int(temp[i]) < firstList[-1]:
						print('-')
						point = 2
						break
				if check == 1:
					if int(temp[i]) >= secondList[-1]:
						secondList.append(int(temp[i]))
						tempSeq.append(2)
					elif firstList[-1] <= int(temp[i]):
						firstList.append(int(temp[i]))
						tempSeq.append(1)
					elif firstList[-1] > int(temp[i]):
						print('-')
						point = 2
						break
		else:
			firstList.append(int(temp[i]))
			tempSeq.append(1)
	if len(secondList) > 0 and len(firstList) > 0 and (point != 2):
		if firstList[-1] > secondList[0]:
			print('-')
			continue
	if point != 2:
		if firstList == sorted(firstList) and secondList == sorted(secondList):
			print(*tempSeq, sep='')
			sequence = []
		else:
			print('-')


import sys

def ok(digits):
	prev = -1
	for digit in digits:
		if digit < prev:
			return False
		prev = digit
	return True

def solve():
	get_input = sys.stdin.readline
	t = int(get_input())
	while t > 0:
		n = int(get_input())
		A = []
		colors = []
		c_append = colors.append
		A_append = A.append
		for d in get_input():
			if d.isdigit():
				A_append(int(d))
		B = sorted(A.copy())
		color_one = []
		color_two = []
		one_append = color_one.append
		two_append = color_two.append
		pA = 0
		pB = 0
		while pA < n:
			a = A[pA]
			b = B[pB]
			if a == b:
				one_append(a)
				c_append('1')
				pA += 1
				pB += 1
			else:
				two_append(a)
				c_append('2')
				pA += 1
		if ok(color_one) and ok(color_two):
			print(''.join(colors))
		else:
			print('-')
		t -= 1
solve()


for _ in range(int(input())):
	n = int(input())
	st = input()
	coloured = [2 for i in range(n)]
	minimized = [9999999999 for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		minimized[i] = min(int(st[i]), minimized[i + 1])
	maximized = [0 for i in range(n)]
	maxi = 0
	for i in range(n):
		maxi = max(maxi, int(st[i]))
		maximized[i] = maxi
	mini = 999999999
	maxi = 999999999
	for i in range(n):
		if minimized[i] != int(st[i]):
			maxi = int(st[i])
			break
	for i in range(n):
		mini = min(mini, minimized[i])
		if mini == int(st[i]) and maxi >= minimized[i]:
			coloured[i] = 1
			mini = 9999999999
		else:
			maxi = min(maxi, int(st[i]))
	coloured1 = []
	coloured2 = []
	for i in range(n):
		if coloured[i] == 1:
			coloured1.append(int(st[i]))
		else:
			coloured2.append(int(st[i]))
	f_coloured = coloured1 + coloured2
	flag = 1
	for i in range(n - 1):
		if f_coloured[i] <= f_coloured[i + 1]:
			pass
		else:
			print('-')
			flag = 0
			break
	if flag == 0:
		continue
	for i in range(n):
		print(coloured[i], end='')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	num = list(input())
	ans = ['2'] * n
	s = sorted(num)
	i = 0
	j = 0
	while i < n:
		if num[i] == s[j]:
			j += 1
			ans[i] = '1'
		i += 1
	new = []
	for i in range(n):
		if ans[i] == '2':
			new.append(num[i])
	f = True
	for i in range(1, len(new)):
		if new[i] < new[i - 1]:
			f = False
	if not f:
		print('-')
	else:
		print(''.join(ans))


import sys
import math
from collections import defaultdict
import heapq
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	s = list(sys.stdin.readline()[:-1])
	l = [0 for x in range(n)]
	for i in range(n):
		l[i] = [s[i], i]
	l.sort()
	(ind2, ind1) = (n, n)
	one = False
	exist = True
	last1 = -1
	done = True
	ans = [0 for x in range(n)]
	for i in range(n - 1, -1, -1):
		if l[i][1] < ind2 and (not one):
			ind2 = l[i][1]
			ans[l[i][1]] = 2
			continue
		if l[i][0] == last1 and l[i][1] < ind2 and done:
			ind2 = l[i][1]
			ans[l[i][1]] = 2
			continue
		else:
			if last1 != -1 and l[i][0] != last1:
				done = False
			last1 = l[i][0]
			if l[i][1] < ind1:
				one = True
				ans[l[i][1]] = 1
				ind1 = l[i][1]
			else:
				exist = False
				break
	if exist:
		print(''.join((str(x) for x in ans)))
	else:
		print('-')


from sys import stdin
t = int(stdin.readline())
for i in range(t):
	n = int(stdin.readline())
	d = stdin.readline(n)
	dic = {}
	right_bound = 0
	min_bound = 0
	flag = False
	for j in range(10):
		j = str(j)
		if right_bound and j in d[:right_bound]:
			flag = True
		for k in range(right_bound, n):
			if j == d[k]:
				right_bound = k
				dic[k] = '1'
				min_bound = j
		if flag:
			break
	right_bound = 0
	for j in range(int(min_bound), 10):
		j = str(j)
		for k in range(right_bound, n):
			if j == d[k] and k not in dic:
				right_bound = k
				dic[k] = '2'
	if len(dic) == n:
		for k in range(n):
			print(dic[k], end='')
		print()
	else:
		print('-')
	c = stdin.readline(1)


for _ in range(int(input())):
	n = int(input())
	li = [int(i) for i in input()]
	sli = sorted(li)
	j = 0
	ans = [-1] * n
	for i in range(n):
		if li[i] == sli[j]:
			ans[i] = 1
			j += 1
	if j == n:
		print(''.join(map(str, ans)))
	else:
		for i in range(n):
			if li[i] == sli[j]:
				ans[i] = 2
				j += 1
			if j == n:
				break
		if j == n:
			print(''.join(map(str, ans)))
		else:
			print('-')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	for k in range(1, 10):
		res = ''
		A = [-1, -2]
		for i in s:
			a = int(i)
			if a < k:
				if a >= A[0]:
					A[0] = a
					res += '1'
				else:
					res = '-'
					break
			elif a >= A[1]:
				A[1] = a
				res += '2'
			elif a == k:
				A[0] = a
				res += '1'
			else:
				res = '-'
				break
		else:
			break
	else:
		res = '-'
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	s = [int(p) for p in list(input())]
	ok = 1
	for avg in range(10):
		check2 = []
		check1 = []
		ans = [0] * n
		for i in range(n):
			if s[i] <= avg:
				if not check1:
					check1.append(s[i])
					ans[i] = '1'
				elif check1[-1] <= s[i]:
					check1.append(s[i])
					ans[i] = '1'
				else:
					ok = 0
					break
			elif s[i] > avg:
				if not check2:
					check2.append(s[i])
					ans[i] = '2'
				elif check2[-1] <= s[i]:
					check2.append(s[i])
					ans[i] = '2'
				elif not check1:
					check1.append(s[i])
				elif check1[-1] <= s[i] <= check2[0]:
					check1.append(s[i])
					ans[i] = '1'
				else:
					ok = 0
					break
		if all(ans):
			print(''.join(ans))
			ok = 1
			break
	if not ok:
		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)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, list(input())))
	flag = 0
	for i in range(0, 10):
		temp = [0 for _ in range(n)]
		first_2 = -1
		for j in range(0, n):
			if a[j] > i:
				temp[j] = 2
				if first_2 == -1:
					first_2 = j
			elif a[j] < i:
				temp[j] = 1
		for j in range(0, n):
			if a[j] == i:
				if first_2 > j:
					temp[j] = 2
				else:
					temp[j] = 1
		one = []
		two = []
		for i in range(0, n):
			if temp[i] == 1:
				one.append(a[i])
			else:
				two.append(a[i])
		final = one + two
		flag = 1
		for i in range(0, n - 1):
			if final[i] > final[i + 1]:
				flag = 0
				break
		if flag == 1:
			print(*temp, sep='')
			break
	if flag == 0:
		print('-')


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('-')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(input())
	b = sorted(a)
	i = 0
	j = 0
	k = []
	l = ['2'] * n
	while i < n:
		if a[i] == b[j]:
			l[i] = '1'
			i = i + 1
			j = j + 1
		else:
			i = i + 1
	c = []
	for i in range(n):
		if l[i] == '1':
			c.append(a[i])
	for i in range(n):
		if l[i] == '2':
			c.append(a[i])
	if c == b:
		print(''.join(l))
	else:
		print('-')


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input()]
	temp = sorted(l)
	res = [-1] * n
	j = 0
	for i in range(n):
		if l[i] == temp[j]:
			j += 1
			res[i] = 1
	if j == len(temp):
		print(*res, sep='')
		continue
	for i in range(n):
		if l[i] == temp[j]:
			j += 1
			res[i] = 2
		if j == len(temp):
			break
	if j == len(temp):
		print(*res, sep='')
	else:
		print('-')


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().strip()]
	d = {i: [] for i in range(10)}
	for i in range(n):
		d[a[i]].append(i)
	sw = 0
	ans = [0] * n
	mn = -1
	ok = True
	for i in range(10):
		if d[i]:
			if d[i][0] > mn:
				mn = d[i][-1]
				for j in d[i]:
					ans[j] = sw + 1
			else:
				if sw:
					ok = False
					break
				nmn = d[i][-1]
				if d[i][-1] > mn:
					for j in d[i]:
						if j < mn:
							ans[j] = 2
							nmn = j
						if j > mn:
							ans[j] = 1
				else:
					for j in d[i]:
						ans[j] = 2
				mn = nmn
				sw = 1
	print(''.join(map(str, ans)) if ok else '-')


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().rstrip()))
		b = [[] for _ in range(10)]
		for i in range(n):
			b[a[i]].append(i)
		ma = max(a)
		one = []
		two = b[ma][::-1]
		for i in range(ma - 1, -1, -1):
			f = 0
			while b[i] and b[i][-1] > two[-1]:
				f = 1
				one.append(b[i].pop())
			while b[i]:
				two.append(b[i].pop())
			if f:
				for j in range(i - 1, -1, -1):
					while b[j]:
						one.append(b[j].pop())
				break
		one.sort()
		two.sort()
		c = []
		for i in one:
			c.append(a[i])
		for i in two:
			c.append(a[i])
		f = 0
		for i in range(n - 1):
			if c[i] > c[i + 1]:
				f = 1
				break
		if f:
			print('-')
		else:
			for i in one:
				a[i] = '1'
			for i in two:
				a[i] = '2'
			print(''.join(a))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()