题目描述

ZJC和他的朋友们正在玩游戏。共有$n$名玩家，玩家$i$的温度值是$i$,环境类型表示为$0$或$1$
当两位棋手在某一特定环境中对战时:

1.如果环境类型为 $0$ ，则在该环境中温度值较低的棋手总是获胜
2.如果环境类型为 $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$ ) - 玩家人数。
每个测试用例的第二行都包含一个长度为 $n-1$ 的二进制字符串 $s$。

输出格式

对于每个测试用例，输出 $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$ 的棋手可以获胜。