CF1774C.Ice and Fire

Little09 and his friends are playing a game. There are $n$ players, and the temperature value of the player $i$ is $i$.

The types of environment are expressed as $0$ or $1$. When two players fight in a specific environment, if its type is $0$, the player with a lower temperature value in this environment always wins; if it is $1$, the player with a higher temperature value in this environment always wins. The types of the $n-1$ environments form a binary string $s$ with a length of $n-1$.

If there are $x$ players participating in the game, there will be a total of $x-1$ battles, and the types of the $x-1$ environments will be the first $x-1$ characters of $s$. While there is more than one player left in the tournament, choose any two remaining players to fight. The player who loses will be eliminated from the tournament. The type of the environment of battle $i$ is $s_i$.

For each $x$ from $2$ to $n$, answer the following question: if all players whose temperature value does not exceed $x$ participate in the game, how many players have a chance to win?

Little09 和他的朋友们正在玩一个游戏。共有 $n$ 名玩家，玩家 $i$ 的温度值为 $i$。

环境类型用 $0$ 或 $1$ 表示。当两名玩家在特定环境中对战时：若该环境类型为 $0$，则温度值较低的玩家总是获胜；若该环境类型为 $1$，则温度值较高的玩家总是获胜。$n-1$ 个环境的类型构成一个长度为 $n-1$ 的二进制字符串 $s$。

若共有 $x$ 名玩家参与游戏，则总共进行 $x-1$ 场对战，这 $x-1$ 场对战所处环境的类型依次为 $s$ 的前 $x-1$ 个字符。只要游戏中剩余玩家数大于 $1$，就任选两名剩余玩家进行对战，失败者将被淘汰。第 $i$ 场对战所处环境的类型为 $s_i$。

对每个从 $2$ 到 $n$ 的 $x$，回答以下问题：若所有温度值不超过 $x$ 的玩家均参与游戏，则有多少名玩家有可能获胜？

Each test contains multiple test cases. The first line contains a single integer $t$ ($1\le t \le 10^3$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2\leq n\leq 2\cdot 10^5$) — the number of players.

The second line of each test case contains a binary string $s$ with a length $n-1$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1\le t \le 10^3$）—— 测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2\leq n\leq 2\cdot 10^5$）—— 玩家数量。

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

保证所有测试用例的 $n$ 值之和不超过 $3\cdot 10^5$。

For each test case output $n-1$ integers — for each $x$ from $2$ to $n$, output the number of players that have a chance to win.

对于每个测试用例，输出 $n-1$ 个整数——对每个从 $2$ 到 $n$ 的 $x$，输出可能获胜的玩家数量。

In the first test case, for $x=2$ and $x=3$, only the player whose temperature value is $1$ can be the winner. For $x=4$, the player whose temperature value is $2,3,4$ can be the winner.

在第一个测试用例中，当 $x=2$ 和 $x=3$ 时，只有温度值为 $1$ 的玩家可以获胜；当 $x=4$ 时，温度值为 $2,3,4$ 的玩家可以获胜。