让我们定义 美女 二进制字符串 $$$z$$$ 的 作为索引 $$$i$$$ 的数量,使得 $$$1 \le i \lt |z|$$$ 和 $$$z_i \neq z_{i+1}$$$。
在等待来自 CCB 的朋友时,Andryusha 烤了一个馅饼,由长度为 $$$n$$$ 的二进制字符串 $$$s$$$ 表示。为了避免得罪任何人,他想把这个字符串分成 $$$k$$$ 个子字符串,使得每个数字都属于一个子字符串,并且所有子字符串的美感都是相同的。
Andryusha 不知道 CCB 的朋友会来他家的确切数量,因此他想找到 $$$k$$$ 的值的数量,从而可以将馅饼分割成具有相同美感的 $$$k$$$ 部分。
然而,Andryusha 的兄弟 Tristan 认为这个问题的表述过于简单。因此,他希望你找到$$$k$$$这样的值的个数 对于字符串的每个前缀。换句话说,对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,您需要找到 $$$k$$$ 的值的数量,对于这些值,可以将前缀 $$$s_1 s_2 \ldots s_i$$$ 拆分为具有相同美感的 $$$k$$$ 部分。
输入
每个测试由多个测试用例组成。输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — 二进制字符串的长度。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串,仅由数字组成 0 和 1.
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,输出一行包含 $$$n$$$ 整数 $$$c_i$$$ ($$$0 \le c_i \le n$$$) — $$$k$$$ 的值的数量,可以将前缀 $$$s_1 s_2 \ldots s_i$$$ 拆分为具有相同美感的 $$$k$$$ 部分。
示例
输入复制
350001110010101010170010100
输出复制
1 2 3 4 5 1 2 2 3 2 4 2 4 3 4 1 2 3 3 4 3 4
注意
第三种情况,满足条件的$$$k$$$的值为:
- $$$i = 1$$$: $$$k \in \{1\}$$$,
- $$$i = 2$$$: $$$k \in \{1, 2\}$$$,
- $$$i = 3$$$: $$$k \in \{1, 2, 3\}$$$,
- $$$i = 4$$$: $$$k \in \{1, 3, 4\}$$$,
- $$$i = 5$$$: $$$k \in \{1, 2, 4, 5\}$$$,
- $$$i = 6$$$: $$$k \in \{1, 5, 6\}$$$,
- $$$i = 7$$$: $$$k \in \{1, 5, 6, 7\}$$$。