Little09 和他的朋友们正在玩游戏。有$$$n$$$个玩家,$$$i$$$玩家的温度值为$$$i$$$。
环境类型表示为 $$$0$$$ 或 $$$1$$$。当两个玩家在特定环境中战斗时,如果其类型为$$$0$$$,则该环境中温度值较低的玩家总是获胜;如果是$$$1$$$,则在该环境下温度值较高的玩家总是获胜。 $$$n-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$$$) — 玩家数量。
每个测试用例的第二行包含一个二进制字符串$$$s$$$,长度为$$$n-1$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3\cdot 10^5$$$。
输出
对于每个测试用例输出 $$$n-1$$$ 整数 - 对于从 $$$2$$$ 到 $$$n$$$ 的每个 $$$x$$$,输出有机会获胜的玩家数量。
示例
输入 #1
2 4 001 4 101
输出 #1
1 1 3 1 2 3
注意
在第一个测试用例中,对于$$$x=2$$$和$$$x=3$$$,只有温度值为$$$1$$$的玩家才能成为获胜者。对于$$$x=4$$$,温度值为$$$2,3,4$$$的玩家可以获胜。