piece of wood set apart with their names. This board of wood can be addressed as a line of n characters. Each character is either a 'D' or a 'K'. You need to make some number of cuts (conceivably 0) on this string, parceling it into a few bordering pieces, each with length something like 1. The two siblings act with poise, so they need to part the wood as equitably as
Correct answer will upvoted else downvoted.
siblings are managing an abnormal piece of wood set apart with their names. This board of wood can be addressed as a line of n characters. Each character is either a 'D' or a 'K'. You need to make some number of cuts (conceivably 0) on this string, parceling it into a few bordering pieces, each with length something like 1. The two siblings act with poise, so they need to part the wood as equitably as could be expected. They need to know the greatest number of pieces you can part the wood into with the end goal that the proportions of the number of events of 'D' to the number of events of 'K' in each lump are something very similar.
Kaeya, the inquisitive scholar, is keen on the answer for a long time. He needs to know the response for each prefix of the given string. Assist him with taking care of this issue!
For a string we characterize a proportion as a:b where 'D' shows up in it multiple times, and 'K' seems b times. Note that an or b can approach 0, however not both. Proportions a:b and c:d are viewed as equivalent if and provided that a⋅d=b⋅c.
For instance, for the string 'DDD' the proportion will be 3:0, for 'DKD' — 2:1, for 'DKK' — 1:2, and for 'KKKKDD' — 2:4. Note that the proportions of the last two strings are equivalent to one another, yet they are not equivalent to the proportions of the initial two strings.
Input
Each test contains various experiments. The primary line contains the number of experiments t (1≤t≤1000). Portrayal of the experiments follows.
The primary line of each experiment contains an integer n (1≤n≤5⋅105) — the length of the wood.
The second line of each experiment contains a string s of length n. Each character of s will be either 'D' or 'K'.
It is ensured that the amount of n over all experiments doesn't surpass 5⋅105.
Output
For each experiment, output n space isolated integers. The I-th of these numbers should approach the response for the prefix s1,s2,… ,si.
Step by step
Solved in 4 steps with 1 images
