Busy Beaver 决定竞选总统。不幸的是，他唯一的竞争对手 Lazy Lemur 实力太强，Busy Beaver 无法通过正常手段获胜。因此，他决定采取所有优秀政客都会做的事：通过杰利蝾螈（选区划分）操纵选举！

Busy Beaver 的国家由 $N$ 个排成一行的城市组成，编号为 $1$ 到 $N$。每个城市投票给 Lazy Lemur 或 Busy Beaver，用 $0$ 表示投给 Lazy Lemur，用 $1$ 表示投给 Busy Beaver。Busy Beaver 可以将这 $N$ 个城市划分为 $K$ 个非空的连续城市块，每一块即为一个选区。对于 $1$ 到 $N$ 的每一个 $K$ 值，Busy Beaver 希望最大化那些投给他的票数严格多于投给 Lazy Lemur 的票数的选区数量。

你能帮 Busy Beaver 找出对于 $K = 1, \dots, N$ 时，他能赢得的选区的最大数量吗？

输入格式

每个测试点包含多个测试用例。第一行包含测试用例数量 $T$ ($1 \le T \le 10^4$)。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $N$ ($1 \le N \le 10^5$)，表示城市数量。

每个测试用例的第二行包含一个长度为 $N$ 的由 $0$ 和 $1$ 组成的字符串 $s$，其中 $s_i$ 为 $0$ 表示 Lazy Lemur 赢得了第 $i$ 个城市的投票，$1$ 表示 Busy Beaver 赢得了第 $i$ 个城市的投票，对于每个 $i$ 从 $1$ 到 $N$。

保证所有测试用例的 $N$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出 $N$ 个整数，其中第 $K$ 个整数表示将城市划分为 $K$ 个非空连续块后，Busy Beaver 赢得的票数严格多于 Lazy Lemur 的选区的最大数量。

子任务

• ($10$ 分) 所有测试用例的 $N$ 之和不超过 $100$。
• ($25$ 分) 所有测试用例的 $N$ 之和不超过 $3000$。
• ($65$ 分) 所有测试用例的 $N$ 之和不超过 $10^5$。

样例

输入格式 1

3
3
000
5
01101
8
11011011

输出格式 1

0 0 0
1 1 2 2 3
1 2 3 4 4 5 5 6

说明

共有 $3$ 个测试用例。

在第一个测试用例中，Busy Beaver 永远无法赢得任何选区，因为每个城市都投给了 Lazy Lemur。

在第二个测试用例中，共有 $5$ 个城市。对于 $K = 3$，Busy Beaver 可以通过将城市划分为子数组 $[1, 3]$、$[4, 4]$ 和 $[5, 5]$ 来赢得 $2$ 个选区。在 $[1, 3]$ 中，有 $2$ 个城市投给了他（超过半数）。他在 $[4, 4]$ 中输了，因为该选区唯一的城市没有投给他。他在 $[5, 5]$ 中赢了，因为该选区唯一的城市投给了他。可以证明 Busy Beaver 最多只能赢得 $2$ 个选区。

注意，如果划分为子数组 $[1, 2]$、$[3, 4]$ 和 $[5, 5]$，他只能赢得 $1$ 个选区。特别地，他在 $[1, 2]$ 和 $[3, 4]$ 中各只赢得了一个城市，因此在这两个选区中都没有获得严格多数。