Ice and Fire

链接：https://codeforces.com/problemset/problem/1774/C
来源：codeforces

时间限制：1 seconds
空间限制：256 megabytes

题目描述

小09和他的朋友在玩游戏。有\(n\)个玩家，其中玩家\(i\)的温度值是\(i\)。

环境的类型表示为\(0\)或\(1\)。当两个玩家在一个特定的环境中战斗时，如果其类型是\(0\)，在这个环境中温度值较低的玩家总是获胜；如果是\(1\)，在这个环境中温度值较高的玩家总是获胜。这些环境的类型构成一个长度为\(n-1\)的二进制字符串\(s\)。

如果有\(x\)个玩家参加比赛，总共会有\(x-1\)场战斗，而\(x-1\)个环境的类型将是\(s\)中对应的\(x-1\)个字符。当比赛中剩下的玩家不止一个时，选择剩下的任何两个玩家进行战斗。输掉比赛的选手将被淘汰出局。战斗\(i\)的环境类型为\(s_i\)。

对于\(2\)到\(n\)中的每一个\(x\)，回答以下问题：如果所有温度值不超过\(x\)的玩家都参与游戏，有多少玩家有机会获胜？

输入

每个测试包含多个测试用例。第一行包含一个整数\(t\)（\(1\le t \le 10^3\)）--测试用例的数量。测试用例的描述如下。

每个测试案例的第一行包含一个整数\(n\)（\(2\leq n\leq 2\cdot 10^5\)）--玩家的数量。

每个测试案例的第二行包含一个长度为\(n-1\)的二进制字符串\(s\)。

保证所有测试案例的\(n\)之和不超过\(3\cdot 10^5\)。

输出

对于每个测试案例输出\(n-1\)个整数--对于从\(2\)到\(n\)的每个\(x\)，输出有机会获胜的玩家数量。

样例

输入样例

2
4
001
4
101

输出样例

1 1 3 
1 2 3 

样例解释

在第一个测试案例中，对于\(x=2\)和\(x=3\)，只有温度值为\(1\)的玩家可以成为赢家。对于\(x=4\)，温度值为\(2,3,4\)的玩家可以成为赢家。