CF1536C.Diluc and Kaeya

The tycoon of a winery empire in Mondstadt, unmatched in every possible way. A thinker in the Knights of Favonius with an exotic appearance.

This time, the brothers are dealing with a strange piece of wood marked with their names. This plank of wood can be represented as a string of $n$ characters. Each character is either a 'D' or a 'K'. You want to make some number of cuts (possibly $0$) on this string, partitioning it into several contiguous pieces, each with length at least $1$. Both brothers act with dignity, so they want to split the wood as evenly as possible. They want to know the maximum number of pieces you can split the wood into such that the ratios of the number of occurrences of 'D' to the number of occurrences of 'K' in each chunk are the same.

Kaeya, the curious thinker, is interested in the solution for multiple scenarios. He wants to know the answer for every prefix of the given string. Help him to solve this problem!

For a string we define a ratio as $a:b$ where 'D' appears in it $a$ times, and 'K' appears $b$ times. Note that $a$ or $b$ can equal $0$, but not both. Ratios $a:b$ and $c:d$ are considered equal if and only if $a\cdot d = b\cdot c$.

For example, for the string 'DDD' the ratio will be $3:0$, for 'DKD' — $2:1$, for 'DKK' — $1:2$, and for 'KKKKDD' — $2:4$. Note that the ratios of the latter two strings are equal to each other, but they are not equal to the ratios of the first two strings.

蒙德城一家葡萄酒帝国的霸主，无论从哪个角度看都无可匹敌。西风骑士团中一位相貌异域、思维深邃的思想者。

这一次，兄弟二人面对一块刻有他们名字的奇异木板。这块木板可表示为一个长度为 $n$ 的字符串，其中每个字符均为 'D' 或 'K'。你希望在此字符串上进行若干次切割（可能为 $0$ 次），将其划分为若干个连续的子串，且每个子串长度至少为 $1$。两兄弟皆以尊严行事，因此希望尽可能均匀地分割这块木板。他们想知道：最多能将木板切成多少段，使得每一段中 'D' 的出现次数与 'K' 的出现次数之比均相同。

身为好奇思想者的凯亚，对多种情形下的解法均感兴趣。他希望知道：对于给定字符串的每一个前缀，该问题的答案分别是多少？请助他解决此问题！

对于一个字符串，我们定义其比率为 $a:b$，其中 'D' 出现 $a$ 次，'K' 出现 $b$ 次。注意：$a$ 与 $b$ 中可有一个为 $0$，但不能同时为 $0$。比率 $a:b$ 与 $c:d$ 被视为相等，当且仅当 $a\cdot d = b\cdot c$。

例如，字符串 'DDD' 的比率为 $3:0$，'DKD' 的比率为 $2:1$，'DKK' 的比率为 $1:2$，而 'KKKKDD' 的比率为 $2:4$。注意：后两个字符串的比率彼此相等，但它们均不等于前两个字符串的比率。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 5 \cdot 10^5$) — the length of the wood.

The second line of each test case contains a string $s$ of length $n$. Every character of $s$ will be either 'D' or 'K'.

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output $n$ space separated integers. The $i$-th of these numbers should equal the answer for the prefix $s_{1},s_{2},\dots,s_{i}$.

对于每个测试用例，输出 $n$ 个以空格分隔的整数。其中第 $i$ 个数应等于前缀 $s_{1},s_{2},\dots,s_{i}$ 对应的答案。

For the first test case, there is no way to partition 'D' or 'DDK' into more than one block with equal ratios of numbers of 'D' and 'K', while you can split 'DD' into 'D' and 'D'.

For the second test case, you can split each prefix of length $i$ into $i$ blocks 'D'.

对于第一个测试用例，无法将字符串 'D' 或 'DDK' 划分为多个块，使得各块中 'D' 与 'K' 的数量之比均相等；但可以将 'DD' 拆分为 'D' 和 'D' 两个块。

对于第二个测试用例，可以将每个长度为 $i$ 的前缀拆分为 $i$ 个块 'D'。