D. 将二进制字符串划分为子序列
每次测试时间限制：$2$ 秒
内存限制：$256$ 兆字节

你有一个由 $n$ 个字符 0 和 1 组成的二进制字符串 $s$。

你的任务是将给定的字符串划分为最少的子序列，使得字符串中的每个字符恰好属于一个子序列，并且每个子序列的形式类似于 "010101..." 或 "101010..."（即子序列中不能包含相邻的两个 0 或两个 1）。

回忆一下，子序列是指通过从原序列中删除零个或多个元素（不改变剩余元素的顺序）得到的序列。例如，"1011101" 的子序列包括 "0"、"1"、"11111"、"0111"、"101"、"1001"，但不包括 "000"、"101010" 和 "11100"。

你需要回答 $t$ 个独立的测试用例。

输入
第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$）——测试用例的数量。
接下来是 $t$ 个测试用例。
每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——字符串 $s$ 的长度。
第二行包含 $n$ 个字符 '0' 和 '1'——字符串 $s$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$（$\sum n \le 2 \cdot 10^5$）。

输出
对于每个测试用例，输出答案：

• 第一行输出一个整数 $k$（$1 \le k \le n$）——划分字符串所需的最少子序列数量。
• 第二行输出 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le k$），其中 $a_i$ 表示第 $i$ 个字符所属的子序列编号。

如果有多个答案，输出任意一个即可。

示例

输入

4
4
0011
6
111111
5
10101
8
01010000

输出

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