题目描述

薯条哥拥有一个长度为$n$的$01$串$s=s_1,s_2,...,s_n$(下标从$1$开始)。

对于每个位置$i(1\le i\le n)$，定义：$a_i$为在$i$左侧(即下标$＜i$的位置)中，字符与$s_i$不同的元素个数。

请你输出整个序列$[a_1,a_2,...a_n]$

输入描述

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

在第一行输入一个整数$n(1\le n\le 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$。