You are given a binary string $s$ consisting of $n$ zeros and ones.

Your task is to divide the given string into the minimum number of subsequences in such a way that each character of the string belongs to exactly one subsequence and each subsequence looks like "010101 ..." or "101010 ..." (i.e. the subsequence should not contain two adjacent zeros or ones).

Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, subsequences of "1011101" are "0", "1", "11111", "0111", "101", "1001", but not "000", "101010" and "11100".

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of $s$. The second line of the test case contains $n$ characters '0' and '1' — the string $s$.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer: in the first line print one integer $k$ ($1 \le k \le n$) — the minimum number of subsequences you can divide the string $s$ to. In the second line print $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), where $a_i$ is the number of subsequence the $i$-th character of $s$ belongs to.

If there are several answers, you can print any.


-----Example-----
Input
4
4
0011
6
111111
5
10101
8
01010000

Output
2
1 2 2 1 
6
1 2 3 4 5 6 
1
1 1 1 1 1 
4
1 1 1 1 1 2 3 4

Difficulty: introductory

Starter code:

Solutions:
import sys

input=sys.stdin.readline

#t=1
t=int(input())
for _ in range(t):
    n=int(input())
    s=input().rstrip()
    s=[s[-i-1] for i in range(n)]
    ans=[]
    zero=[]
    one=[]
    res=[-1]*n
    pos=0
    while s:
        b=s.pop()
        if b=="0":
            if not one:
                new=1
                ans.append(new)
                res[pos]=len(ans)
                zero.append(len(ans)-1)
            else:
                id=one.pop()
                ans[id]+=1
                res[pos]=id+1
                zero.append(id)
        else:
            if not zero:
                new=1
                ans.append(new)
                res[pos]=len(ans)
                one.append(len(ans)-1)
            else:
                id=zero.pop()
                ans[id]+=1
                res[pos]=id+1
                one.append(id)
        pos+=1
    print(len(ans))
    print(*res)


import sys
input = sys.stdin.readline
from collections import deque
t = int(input())
for _ in range(t):
  n = int(input())
  a = input()
  ls = []
  st0 = deque()
  st1 = deque()
  for i in range(n):
    if a[i] == "0":
      if st1:
        x = st1.popleft()
        st0.append(x)
      elif st0:
        x = st0[-1]+1
        st0.append(x)
      else:
        x = 1
        st0.append(x)
    else:
      if st0:
        x = st0.pop()
        st1.appendleft(x)
      elif st1:
        x = st1[-1]+1
        st1.append(x)
      else:
        x = 1
        st1.append(x)
    ls.append(x)
  print(max(ls))
  print(*ls)

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


for _ in range(val()):
    n = val()
    l = li3()

    d = defaultdict(list)
    ans = {}
    curr = 1
    for i in range(n):
        if len(d[1 - l[i]]):
            d[l[i]].append(d[1 - l[i]].pop())
            ans[i] = d[l[i]][-1]
        else:
            d[l[i]].append(curr)
            ans[i] = curr
            curr += 1
    print(curr - 1)
    for i in range(n):
        print(ans[i], end = ' ')
    print()

for _ in range(int(input())):
    n = int(input())
    s = list(input())
    
    result = [0] * n
    
    ones = []
    zeroes = []
    current = 1
    
    for i in range(n):
        if s[i] == '0':
            if len(zeroes) == 0:
                ones.append(current)
                result[i] = current
                current += 1
            else:
                x = zeroes.pop()
                result[i] = x
                ones.append(x)
        else:
            if len(ones) == 0:
                zeroes.append(current)
                result[i] = current
                current += 1
            else:
                x = ones.pop()
                result[i] = x
                zeroes.append(x)
    print(current - 1)
    print(*result)
                
                


def solve():
    n = int(input())
    s = input()
    z, o = [], []
    c = 0
    ans = []
    def add(x):
        nonlocal z, o, c, ans
        u, v = z, o
        if x == 0:
            u, v = v, u
        if u:
            w = u.pop()
            ans.append(w)
            v.append(w)
        else:
            c += 1
            ans.append(c)
            v.append(c)
    for i in s:
        add(int(i))
    print(c)
    print(*ans)

t = int(input())
for _ in range(t):
    solve()

t = int(input())

for _ in range(t):
    n = int(input())
    s = list(map(int, input()))
    
    zeros = []
    ones = []
    count = 0
    ans = []
    
    for d in s:
        if d == 0:
            if zeros:
                ans.append(zeros[-1])
                ones.append(zeros.pop())
            else:
                count += 1
                ans.append(count)
                ones.append(count)
        else:
            if ones:
                ans.append(ones[-1])
                zeros.append(ones.pop())
            else:
                count += 1
                ans.append(count)
                zeros.append(count)
                
    print(count)
    print(*ans)


#Bhargey Mehta (Junior)
#DA-IICT, Gandhinagar
import sys, math
mod = 10**9

def solve(test_index):
    n = int(input())
    s = input()
    a, b = [], []
    p = 0
    ans = []
    for c in s:
        if c == '0':
            if len(a) == 0:
                p += 1
                ans.append(p)
                b.append(p)
            else:
                seq = a.pop()
                ans.append(seq)
                b.append(seq)
        else:
            if len(b) == 0:
                p += 1
                ans.append(p)
                a.append(p)
            else:
                seq = b.pop()
                ans.append(seq)
                a.append(seq)
    print(p)
    print(*ans)
    return

if 'PyPy' not in sys.version:
    sys.stdin = open('input.txt', 'r')

sys.setrecursionlimit(100000)
num_tests = 1
num_tests = int(input())
for test in range(1, num_tests+1):
    #print("Case #{}: ".format(test), end="")
    solve(test)


from sys import stdin
import sys

tt = int(stdin.readline())

for loop in range(tt):

    n = int(stdin.readline())
    a = stdin.readline()
    a = a[:-1]

    zero = []
    one  = []
    ans  = []

    for i in a:
        if i == "0":
            if len(zero) == 0:
                zero.append(len(zero)+len(one)+1)
            ans.append(zero[-1])
            one.append(zero[-1])
            del zero[-1]
        else:
            if len(one) == 0:
                one.append(len(zero)+len(one)+1)
            ans.append(one[-1])
            zero.append(one[-1])
            del one[-1]

    print(len(zero) + len(one))
    print(*ans)
            

    


mod = 10**9 + 7
def solve():
    n = int(input())
    s = input()
    s0 = []
    s1 = []
    vec = []
    sm = 0
    for i in range(n):
        if s[i] == '1':
            if(len(s0) < 1):
                sm += 1
                s1.append(sm)
                vec.append(sm)
            else:
                vec.append(s0[len(s0) - 1])
                s1.append(s0[len(s0) - 1])
                s0.pop()
        else:
            if (len(s1) < 1):
                sm += 1
                s0.append(sm)
                vec.append(sm)
            else:
                vec.append(s1[len(s1) - 1])
                s0.append(s1[len(s1) - 1])
                s1.pop()
    print(sm)
    print(*vec, sep = ' ')
t = 1
t = int(input())
for _ in range(t):
    solve()

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    ans = [0] * n
    max_elem = 0
    want_indices = [[], []] #want_indices[0] means the index wants 0
    for i, d in enumerate(map(int, s)):
        if not want_indices[d]:
            max_elem += 1
            ans[i] = max_elem
            want_indices[1 - d].append(max_elem)
        else:
            index = want_indices[d].pop()
            ans[i] = index
            want_indices[1 - d].append(index)
    print(max_elem)
    print(*ans, sep = ' ')



#!/usr/bin/env pypy3

from sys import stdin, stdout
 
def input():
    return stdin.readline().strip()

def ans(S):

	num_0 = []
	num_1 = []

	ret = []

	for c in S:
		if c == '0':
			if len(num_1) == 0:
				# create new
				num_0 += [(len(num_0) + len(num_1))]
			else:
				num_0 += [num_1.pop()]

			ret += [num_0[-1] + 1]


		else:
			assert(c == '1')

			if len(num_0) == 0:
				# create new
				num_1 += [(len(num_0) + len(num_1))]
			else:
				num_1 += [num_0.pop()]

			ret += [num_1[-1] + 1]


	return len(num_0) + len(num_1), ret


	return S

T = int(input())
for t in range(T):
	input()
	S = input()
	
	p, q = ans(S)
	print(p)
	print(*q)


for _ in range(int(input())):
    n = int(input())
    a = list(input())
    n1 = []
    n0 = []
    ans = []
    c1 = 0
    c0 = 0
    curr = 1
    for i in a:
        if i == '1':
            if c0>0:
                c1 += 1
                c0 -= 1
                ans.append(n0[-1])
                n1.append(n0[-1])
                n0.pop()
            else:
                c1 += 1
                ans.append(curr)
                n1.append(curr)
                curr += 1
        else:
            if c1>0:
                c0 += 1
                c1 -= 1
                ans.append(n1[-1])
                n0.append(n1[-1])
                n1.pop()
            else:
                c0 += 1
                ans.append(curr)
                n0.append(curr)
                curr += 1
    print(c1+c0)
    print(*ans)

# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

#処理内容
def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		s = list(map(int, list(input())))
		ans = [None] * N
		zeroend = []
		oneend = []
		zero_len = 0
		one_len = 0
		val = 0
		for i in range(N):
			if s[i] == 0:
				if one_len == 0:
					val += 1
					ans[i] = val
					zeroend.append(val)
					zero_len += 1
				else:
					itr = oneend.pop()
					ans[i] = itr
					one_len -= 1
					zeroend.append(itr)
					zero_len += 1
			else:
				if zero_len == 0:
					val += 1
					ans[i] = val
					oneend.append(val)
					one_len += 1
				else:
					itr = zeroend.pop()
					ans[i] = itr
					zero_len -= 1
					oneend.append(itr)
					one_len += 1

		print(val)
		print(*ans)

def __starting_point():
	main()
__starting_point()