蒙德酒庄帝国大亨,各方面都无与伦比。法沃尼斯骑士团中的思想家,有着异国情调的外表。
这一次,兄弟俩正在处理一块刻有他们名字的奇怪木头。这块木板可以表示为一串 $$$n$$$ 字符。每个字符要么是“D”,要么是“K”。您想要对该字符串进行一些切割(可能是 $$$0$$$),将其划分为几个连续的片段,每个片段的长度至少为 $$$1$$$。兄弟俩行事都很有尊严,所以他们想尽可能均匀地劈木头。他们想知道可以将木材分成多少块,以使每个块中“D”出现的次数与“K”出现的次数的比率相同。
Kaeya,一位好奇的思考者,对多种场景的解决方案感兴趣。他想知道给定字符串的每个前缀的答案。帮他解决这个问题吧!
对于字符串,我们将比率定义为 $$$a:b$$$,其中“D”出现在其中 $$$a$$$ 次,“K”出现 $$$b$$$ 次。请注意,$$$a$$$ 或$$$b$$$ 可以等于$$$0$$$,但不能两者都相等。当且仅当 $$$a\cdot d = b\cdot c$$$ 时,比率 $$$a:b$$$ 和 $$$c:d$$$ 被视为相等。
例如,对于字符串 'DDD',比率将为 $$$3:0$$$,对于 'DKD' - $$$2:1$$$,对于 'DKK' - $$$1:2$$$,对于 'KKKKDD' - $$$2:4$$$。请注意,后两个字符串的比率彼此相等,但它们不等于前两个字符串的比率。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — 木材的长度。
每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$s$$$。 $$$s$$$ 的每个字符都是“D”或“K”。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$n$$$ 空格分隔的整数。这些数字中的第 $$$i$$$ 应等于前缀 $$$s_{1},s_{2},\dots,s_{i}$$$ 的答案。
示例
输入 #1
5 3 DDK 6 DDDDDD 4 DKDK 1 D 9 DKDKDDDDK
输出 #1
1 2 1 1 2 3 4 5 6 1 1 1 2 1 1 1 1 2 1 2 1 1 3
注意
对于第一个测试用例,无法将“D”或“DDK”划分为多个具有相同比例“D”和“K”数量的块,而您可以将“DD”拆分为“D”和“D”。
对于第二个测试用例,您可以将长度 $$$i$$$ 的每个前缀拆分为 $$$i$$$ 块“D”。