解题思路

给定长度为 $n$ 的 01 串 $s=s_1s_2\ldots s_n$，要求对每个位置 $i$，统计在它左侧（下标 $< i$）与 $s_i$ 不同的字符个数。 我们可以采用前缀计数的方法：

1. 定义两个变量 cnt0 和 cnt1，分别记录当前已遍历字符中 '0' 和 '1' 的个数。

2. 对每个位置 $i$：

   • 若 $s_i='0'$，则左侧与它不同的字符即为所有已出现的 '1'，即 $a_i = \text{cnt1}$；
   • 若 $s_i='1'$，则 $a_i = \text{cnt0}$。

题目内容

牛牛拥有一个长度为$n$的$01$串$s$=“$s_1s_2...s_n$”(下标从$1$开始)。

对于每个位置$i(1≤i≤n)$，定义：

• $a_i$为在$i$左侧(即下标$＜i$的位置)中，字符与$s_i$不同的元素个数。

  请你输出整个序列{$a_1,a_2,...a_n$}

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≤T≤100)$代表数据组数,每组测试数据描述如下:

在第一行输入一个整数$n(1≤n≤10^3)$，表示字符串长度。

在第二行输入一个长度为$n$,仅由字符'$0$'和'$1$'组成的字符串$s$,表示初始字符串。

输出描述

于每组测试数据，新起一行，按顺序输出$n$个整数$a_1,a_2,...,a_n$相邻整数之间用一个空格分隔。

样例1

输入

2
4
1101
5
01010

输出

0 0 2 1
0 1 1 2 2

说明

对于第一组测试数据：

• 位置$1$：左侧无字符，$a_1=0$；
• 位置2：左侧只有'$1$'，与$s_2$='$1$'相同，$a_2=0$；
• 位置3：$s_3$='$0$'左侧有两个'$1$'，故$a_3=2$:
• 位置4：$s_4$='$1$'，左侧有一个'$0$'，故$a_4=1$。