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⋅ d = b⋅ 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.

Input

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

The first line of each test case contains an integer n (1 ≤ n ≤ 5 ⋅ 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 ⋅ 10^5.

Output

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},...,s_{i}.

Example

Input


5
3
DDK
6
DDDDDD
4
DKDK
1
D
9
DKDKDDDDK


Output


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

Note

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'.

Source: codeforces | Difficulty: MEDIUM
Tags: Number theory

Dynamic programming

Data structures

String algorithms


Solutions:
from math import *
from collections import Counter, defaultdict, deque
I = lambda : int(input())
M = lambda : map(int, input().split())
LI = lambda : list(map(int, input().split()))
for _ in range(I()):
	n = I()
	s = input()
	dc = 0
	kc = 0
	d = defaultdict(int)
	for i in s:
		dc += i == 'D'
		kc += i == 'K'
		g = gcd(dc, kc)
		d[dc // g, kc // g] += 1
		print(d[dc // g, kc // g], end=' ')
	print()


def solve(s, n):
	res = []
	cnt_d = 0
	cnt_k = 0
	h = {}
	i = 0
	while i < n:
		if s[i] == 'D':
			cnt_d += 1
		else:
			cnt_k += 1
		if cnt_d == 0 or cnt_k == 0:
			res.append(cnt_d or cnt_k or 1)
		elif cnt_d / cnt_k in h:
			h[cnt_d / cnt_k] += 1
			res.append(h[cnt_d / cnt_k])
		else:
			h[cnt_d / cnt_k] = 1
			res.append(1)
		i += 1
	return res
for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = solve(s, n)
	print(*ans)


import sys
from math import gcd, sqrt
from typing import DefaultDict
sys.setrecursionlimit(10 ** 5)
inf = float('inf')
en = lambda x: list(enumerate(x))
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())

def solve():
	n = ii()
	s = input()
	arr = []
	brr = []
	a = b = 0
	for i in s:
		if i == 'D':
			a += 1
		else:
			b += 1
		arr += (a,)
		brr += (b,)
	ok = DefaultDict(lambda : 0)
	for (i, j) in zip(arr, brr):
		if j == 0:
			print(i, end=' ')
		elif i == 0:
			print(j, ' ')
		else:
			ratio = i / j
			if ok[ratio]:
				print(ok[ratio] + 1, end=' ')
			else:
				print(1, end=' ')
			ok[ratio] += 1
	print()
for _ in range(ii()):
	solve()


import sys, math
from collections import deque, defaultdict
import operator as op
from functools import reduce
from itertools import permutations
import heapq
I = sys.stdin.readline
alpha = 'abcdefghijklmnopqrstuvwxyz'

def ii():
	return int(I().strip())

def li():
	return list(map(int, I().strip().split()))

def mi():
	return map(int, I().strip().split())

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def isPrime(n):
	if n <= 1:
		return False
	elif n <= 2:
		return True
	else:
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True

def main():
	for _ in range(ii()):
		n = ii()
		s = I().strip()
		dic = defaultdict(int)
		dic[0, 0] = 0
		dic[1, 1] = 0
		ans = []
		d = 0
		k = 0
		for i in s:
			if i == 'D':
				d += 1
			else:
				k += 1
			if d == 0:
				dic[d, k] = dic[d, k - 1] + 1
				ans.append(dic[d, k])
			elif k == 0:
				dic[d, k] = dic[d - 1, k] + 1
				ans.append(dic[d, k])
			else:
				x = math.gcd(d, k)
				d1 = d // x
				k1 = k // x
				dic[d1, k1] += 1
				ans.append(dic[d1, k1])
		print(*ans)
main()


import math
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	s = input()
	dp = [0] * n
	mp = dict()
	a = 0
	b = 0
	(d, k) = (0, 0)
	for i in range(n):
		if s[i] == 'D':
			d += 1
		else:
			k += 1
		(a, b) = (d, k)
		g = math.gcd(a, b)
		a = a // g
		b = b // g
		if (a, b) in mp:
			dp[i] = dp[mp[a, b]] + 1
		else:
			dp[i] = 1
		mp[a, b] = i
	print(*dp)


import sys
import math
import random
import heapq
input = sys.stdin.readline

def pow(a, n, m):
	if n == 0:
		return 1
	x = pow(a, n // 2, m)
	if n % 2 == 0:
		return x * x % m
	else:
		return x * x * a % m

def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
t = int(input())
while t > 0:
	n = int(input())
	s = input().strip()
	ans = []
	di = {}
	d = 0
	k = 0
	for i in s:
		if i == 'D':
			d += 1
		else:
			k += 1
		g = gcd(max(d, k), min(d, k))
		x = d // g
		y = k // g
		if (x, y) in di:
			ans.append(di[x, y] + 1)
			di[x, y] += 1
		else:
			ans.append(1)
			di[x, y] = 1
	print(' '.join(map(str, ans)))
	t -= 1


import sys
from math import gcd
from collections import defaultdict

def I():
	return int(sys.stdin.readline().rstrip())

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def LI2():
	return list(map(int, sys.stdin.readline().rstrip()))

def S():
	return sys.stdin.readline().rstrip()

def LS():
	return list(sys.stdin.readline().rstrip().split())

def LS2():
	return list(sys.stdin.readline().rstrip())

def divisor(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
			if i != n // i:
				res.append(n // i)
	return res
t = I()
for _ in range(t):
	n = I()
	T = S()
	count_D = [0] * (n + 1)
	for i in range(1, n + 1):
		t = T[i - 1]
		count_D[i] = count_D[i - 1]
		if t == 'D':
			count_D[i] += 1
	ratio = defaultdict(int)
	ANS = [1] * (n + 1)
	for i in range(1, n + 1):
		d = count_D[i]
		g = gcd(d, i - d)
		r = (d // g, (i - d) // g)
		x = ratio[r]
		ANS[i] = x + 1
		ratio[r] += 1
	print(*ANS[1:])


from math import gcd

def f(a):
	dct = {}
	(d, k) = (0, 0)
	for i in a:
		if i == 'D':
			d += 1
		else:
			k += 1
		hcf = gcd(d, k)
		l = (d / hcf, k / hcf)
		dct[l] = dct.get(l, 0) + 1
		print(dct[l], end=' ')
for i in range(int(input())):
	a = input().strip()
	lst = input().strip()
	f(lst)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	n = inp()
	s = st()
	d = defaultdict(int)
	(a, b) = (0, 0)
	for i in range(n):
		a += s[i] == 'D'
		b += s[i] == 'K'
		c = gcd(a, b)
		prl(d[a // c, b // c] + 1)
		d[a // c, b // c] += 1
	print()
for _ in range(inp()):
	solve()


import math
t = int(input())
for T in range(t):
	n = int(input())
	data = input()
	D = 0
	K = 0
	dic = {}
	for i in range(len(data)):
		if data[i] == 'D':
			D += 1
		else:
			K += 1
		if D > 0 and K > 0:
			g = math.gcd(D, K)
			d = D / g
			k = K / g
		else:
			d = 0
			k = 0
		if (d, k) in dic:
			dic[d, k] += 1
		else:
			dic[d, k] = 1
		print(dic[d, k], end=' ')
	print('')


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for tc in range(int(input())):
	n = int(input())
	s = input()
	(a, b) = (0, 0)
	cnt = {}
	for i in s:
		a += i == 'D'
		b += i == 'K'
		(x, y) = (a / gcd(a, b), b / gcd(a, b))
		if (x, y) in cnt:
			cnt[x, y] += 1
		else:
			cnt[x, y] = 1
		print(cnt[x, y], end=' ')
	print()


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	s = input().strip()
	ans = []
	(td, tk) = (0, 0)
	h = {}
	for i in range(len(s)):
		if s[i] == 'D':
			td += 1
		else:
			tk += 1
		if tk == 0:
			val = -1
		else:
			val = td / tk
		if val not in h:
			h[val] = 1
		else:
			h[val] += 1
		ans.append(h[val])
	print(*ans)
for _ in range(int(input())):
	solve()


import io
import os
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappush, heappop, heapify
from math import gcd, inf

def solve(N, S):
	prefD = [0]
	prefK = [0]
	for x in S:
		prefD.append(prefD[-1] + (x == 'D'))
		prefK.append(prefK[-1] + (x == 'K'))
	ans = []
	ratioToBest = defaultdict(int)
	for i in range(1, N + 1):
		numSplits = 1
		d0 = prefD[i]
		k0 = prefK[i]
		g = gcd(d0, k0)
		ratio = (d0 // g, k0 // g)
		numSplits = ratioToBest[ratio] + 1
		ratioToBest[ratio] = numSplits
		ans.append(numSplits)
	return ' '.join(map(str, ans))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N,) = [int(x) for x in input().split()]
	S = input().decode().rstrip()
	ans = solve(N, S)
	print(ans)


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
d = ['YES', 'NO']
for _ in range(t):
	n = int(input())
	l = list(input())
	a = 0
	b = 0
	d = defaultdict(lambda : 0)
	for i in range(n):
		if l[i] == 68:
			a += 1
		else:
			b += 1
		c = math.gcd(a, b)
		x = a // c
		y = b // c
		d[x, y] += 1
		print(d[x, y], end=' ')
	print('')


import sys
import math
from typing import DefaultDict
mod = 10 ** 9 + 7
LI = lambda : [int(k) for k in input().split()]
input = lambda : sys.stdin.readline().rstrip()
IN = lambda : int(input())
S = lambda : input()
r = range
for t in r(IN()):
	n = IN()
	s = S()
	d = 0
	k = 0
	rat = DefaultDict(int)
	ans = [0] * n
	ind = 0
	for ele in s:
		if ele == 'D':
			d += 1
		else:
			k += 1
		if min(d, k) == 0:
			ans[ind] = max(d, k)
		else:
			rat[d / k] += 1
			ans[ind] = rat[d / k]
		ind += 1
	print(*ans)


import math

def solve(n: int, s: str) -> None:
	D = 0
	K = 0
	count = {}
	for i in range(n):
		if s[i] == 'D':
			D += 1
		else:
			K += 1
		gcd = math.gcd(D, K)
		x = D // gcd
		y = K // gcd
		if (x, y) in count:
			count[x, y] += 1
		else:
			count[x, y] = 1
		print(count[x, y], end=' ')
	print()
	return
test_cases = int(input())
for _ in range(test_cases):
	n = int(input())
	s = input()
	solve(n, s)


import sys
import math
input = sys.stdin.readline
imp = 'IMPOSSIBLE'
t = int(input())
for test in range(t):
	n = int(input())
	if test == t - 1:
		s = input()
	else:
		s = input()[:-1]
	d = 0
	k = 0
	res = []
	rat = {}
	for i in range(n):
		if s[i] == 'D':
			d += 1
		else:
			k += 1
		if d and k:
			g = math.gcd(d, k)
			ranew = (d // g, k // g)
		elif d:
			ranew = (1, 0)
		else:
			ranew = (0, 1)
		if ranew in rat.keys():
			rat[ranew] += 1
		else:
			rat[ranew] = 1
		res.append(rat[ranew])
	resres = [str(rr) for rr in res]
	print(' '.join(resres))


def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	if b % a == 0:
		return a
	return gcd(b % a, a)

def make_tuple(c):
	(a, b) = c
	if a == 0:
		return (0, 1)
	if b == 0:
		return (1, 0)
	g = gcd(a, b)
	return (a // g, b // g)

def process(S):
	d = {}
	n = len(S)
	count = [0, 0]
	answer = []
	for i in range(n):
		if S[i] == 'D':
			count[0] += 1
		else:
			count[1] += 1
		t = make_tuple(count)
		if t not in d:
			d[t] = 0
		d[t] += 1
		answer.append(d[t])
	return answer
t = int(input())
for i in range(t):
	n = int(input())
	S = input()
	answer = process(S)
	print(' '.join(map(str, answer)))


from math import gcd
for _ in range(int(input())):
	n = int(input())
	s = input()
	cnt = {'D': 0, 'K': 0}
	d = {}
	for c in s:
		cnt[c] += 1
		r = gcd(cnt['D'], cnt['K'])
		(rd, rk) = (cnt['D'] // r, cnt['K'] // r)
		if (rd, rk) not in d:
			d[rd, rk] = 0
		d[rd, rk] += 1
		print(d[rd, rk], end=' ')
	print()


def gcd(a, b):
	if not a or not b:
		return a + b
	return gcd(max(a, b) % min(a, b), min(a, b))
for testis in range(int(input())):
	n = int(input())
	s = input()
	d = {}
	cd = ck = 0
	for x in s:
		if x == 'D':
			cd += 1
		else:
			ck += 1
		a = (cd / gcd(cd, ck), ck / gcd(cd, ck))
		if a in d:
			d[a] += 1
		else:
			d[a] = 1
		print(d[a])


from collections import defaultdict
from math import *
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	g = defaultdict(int)
	k = 0
	d = 0
	for i in s:
		if i == 'K':
			k += 1
		if i == 'D':
			d += 1
		g[k // gcd(k, d), d // gcd(k, d)] += 1
		print(g[k // gcd(k, d), d // gcd(k, d)], end=' ')
	print()


from math import gcd
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	ans = [1] * n
	(lo, hi) = (0, n)
	cnt = {'K': 0, 'D': 0}
	ratio = {'K': 0, 'D': 0}
	pairs = defaultdict(int)
	for i in range(n):
		cnt[s[i]] += 1
		g = gcd(cnt['D'], cnt['K'])
		pairs[cnt['D'] // g, cnt['K'] // g] += 1
		print(pairs[cnt['D'] // g, cnt['K'] // g], end=' ')
	print()


import sys
input = sys.stdin.readline

def I():
	return input().strip()

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import copy, string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, combinations, groupby
from operator import itemgetter
for _ in range(II()):
	n = II()
	a = I()
	currD = 0
	currK = 0
	dic = defaultdict(lambda : 0)
	mex = 0
	ans = [None] * n
	for i in range(n):
		if a[i] == 'D':
			currD += 1
		else:
			currK += 1
		left = currD // math.gcd(currK, currD)
		right = currK // math.gcd(currK, currD)
		key = str(left) + ':' + str(right)
		dic[key] += 1
		mex = dic[key]
		ans[i] = mex
	print(*ans)


from sys import stdin
from math import gcd
from collections import Counter
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s = input().rstrip()
	d = [0]
	k = [0]
	ans = []
	cnt = Counter()
	for c in s:
		if c == 'D':
			d.append(d[-1] + 1)
			k.append(k[-1])
		else:
			k.append(k[-1] + 1)
			d.append(d[-1])
		if d[-1] == 0:
			a = 0
			b = 1
		elif k[-1] == 0:
			b = 0
			a = 1
		else:
			g = gcd(d[-1], k[-1])
			a = d[-1] // g
			b = k[-1] // g
		ans.append(cnt[a, b] + 1)
		cnt[a, b] += 1
	print(*ans)


def reducefract(n, d):

	def gcd(n, d):
		while d != 0:
			t = d
			d = n % d
			n = t
		return n
	greatest = gcd(n, d)
	n /= greatest
	d /= greatest
	return (int(n), int(d))
for _ in range(int(input())):
	dic = {}
	n = int(input())
	s = input()
	(cntd, cntk) = (0, 0)
	for i in range(n):
		if s[i] == 'D':
			cntd += 1
		else:
			cntk += 1
		(x, y) = reducefract(cntd, cntk)
		if (x, y) in dic:
			dic[x, y] += 1
		else:
			dic[x, y] = 1
		print(dic[x, y], end=' ')
	print('\n')


import sys
input = sys.stdin.readline
from math import gcd
t = int(input())
for tests in range(t):
	n = int(input())
	S = input().strip()
	ANS = []
	DICT = dict()
	D = 0
	K = 0
	for s in S:
		if s == 'D':
			D += 1
		else:
			K += 1
		G = gcd(D, K)
		if (D // G, K // G) in DICT:
			DICT[D // G, K // G] += 1
		else:
			DICT[D // G, K // G] = 1
		ANS.append(DICT[D // G, K // G])
	print(*ANS)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = [0] * n
	d = 0
	ans[0] = 1
	m = {}
	if s[0] == 'D':
		d = 1
		m[1, 0] = 1
	else:
		m[0, 1] = 1
	for i in range(1, n):
		if s[i] == 'D':
			d += 1
		g = gcd(d, i + 1 - d)
		(a, b) = (d // g, (i + 1 - d) // g)
		if (a, b) not in m:
			m[a, b] = 1
		else:
			m[a, b] += 1
		ans[i] = m[a, b]
	print(*ans)


from collections import Counter
from math import gcd

def chunks(n, s):
	R = Counter()
	d = 0
	k = 0
	L = []
	for (i, c) in enumerate(s, 1):
		if c == 'D':
			d += 1
		else:
			k += 1
		g = gcd(d, k)
		r = (d // g, k // g)
		R[r] += 1
		L.append(R[r])
	return L

def main():
	t = readint()
	print('\n'.join((' '.join(map(str, chunks(readint(), input()))) for _ in range(t))))
import sys

def readint():
	return int(input())

def readinti():
	return map(int, input().split())

def readintt():
	return tuple(readinti())

def readintl():
	return list(readinti())

def readinttl(k):
	return [readintt() for _ in range(k)]

def readintll(k):
	return [readintl() for _ in range(k)]

def log(*args, **kwargs):
	print(*args, **kwargs, file=sys.stderr)
main()


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
for _ in range(I()):
	n = I()
	s = S()
	cnt = [0, 0]
	freq = defaultdict(int)
	ans = [0] * n
	for (i, x) in enumerate(s):
		x = 1 if x == s[0] else 0
		cnt[x] += 1
		g = gcd(*cnt)
		f = cnt[0] // g / (cnt[1] / g)
		ans[i] = freq[f] = freq[f] + 1
	print(*ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = input()
	dpD = [0 for x in range(n)]
	dpK = [0 for x in range(n)]
	ratios = {}
	count = [1 for _ in range(n)]
	if l[0] == 'D':
		dpD[0] = 1
		ratios[-1] = 1
	else:
		dpK[0] = 1
		ratios[0] = 1
	for end in range(1, n):
		if l[end] == 'D':
			dpD[end] = dpD[end - 1] + 1
			dpK[end] = dpK[end - 1]
		else:
			dpK[end] = dpK[end - 1] + 1
			dpD[end] = dpD[end - 1]
		if dpK[end] == 0:
			ratio = -1
		else:
			ratio = dpD[end] / dpK[end]
		if ratio in ratios:
			ratios[ratio] += 1
			count[end] = ratios[ratio]
		else:
			ratios[ratio] = 1
	print(*count)


import math
t = int(input())
for i in range(0, t):
	n = int(input())
	s = input()
	d = {}
	c1 = 0
	c2 = 0
	for j in range(0, n):
		if s[j] == 'D':
			c1 += 1
		else:
			c2 += 1
		d[c1 // math.gcd(c1, c2), c2 // math.gcd(c1, c2)] = 0
	c1 = 0
	c2 = 0
	for j in range(0, n):
		if s[j] == 'D':
			c1 += 1
		else:
			c2 += 1
		d[c1 // math.gcd(c1, c2), c2 // math.gcd(c1, c2)] += 1
		print(d[c1 // math.gcd(c1, c2), c2 // math.gcd(c1, c2)], end=' ')
	print()


from collections import Counter
from math import gcd
for ti in range(int(input())):
	n = int(input())
	S = input()
	C = Counter()
	(a, b) = (0, 0)
	for s in S:
		if s == 'D':
			a += 1
		else:
			b += 1
		g = gcd(a, b)
		k = (a / g, b / g)
		C[k] += 1
		print(C[k], end=' ')
	print()


from math import gcd
import sys
input = sys.stdin.readline

def main():
	N = int(input())
	S = input()
	Ans = []
	Ratio = dict()
	D = []
	K = []
	d = 0
	k = 0
	for i in range(N):
		if S[i] == 'D':
			d += 1
		else:
			k += 1
		G = gcd(d, k)
		R = (d // G, k // G)
		if R not in Ratio:
			Ratio[R] = 1
		else:
			Ratio[R] += 1
		Ans.append(Ratio[R])
		D.append(d)
		K.append(k)
	print(*Ans)
T = int(input())
for _ in range(T):
	main()


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LI1():
	return list(map(int1, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
inf = 10 ** 16
md = 998244353
from math import gcd
from collections import Counter
for testcase in range(II()):
	n = II()
	s = BI()
	c0 = c1 = 0
	ans = []
	cnt = Counter()
	for c in s:
		if c == 68:
			c0 += 1
		else:
			c1 += 1
		g = gcd(c0, c1)
		cur = (c0 // g, c1 // g)
		cnt[cur] += 1
		ans.append(cnt[cur])
	print(*ans)


from sys import stdin, stdout
from heapq import heapify, heappush, heappop, heappushpop
from collections import defaultdict as dd, deque as dq, Counter as C
from bisect import bisect_left as bl, bisect_right as br
from itertools import combinations as cmb, permutations as pmb
from math import factorial as f, ceil, gcd, sqrt, log, inf
mi = lambda : map(int, input().split())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
mati = lambda r: [li() for _ in range(r)]
lcm = lambda a, b: a * b // gcd(a, b)
MOD = 10 ** 9 + 7

def soe(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def ncr(n, r):
	(p, k) = (1, 1)
	if n - r < r:
		r = n - r
	if r != 0:
		while r:
			(p, k) = (p * n, k * r)
			m = gcd(p, k)
			(p, k) = (p // m, k // m)
			(n, r) = (n - 1, r - 1)
	else:
		p = 1
	return p

def solve():
	n = ii()
	arr = [x for x in input()]
	pf = []
	(a, b) = (0, 0)
	d = {}
	for x in range(n):
		if arr[x] == 'D':
			a += 1
		else:
			b += 1
		g = gcd(a, b)
		if (a // g, b // g) in d:
			print(d[a // g, b // g] + 1, end=' ')
			d[a // g, b // g] += 1
		else:
			print('1', end=' ')
			d[a // g, b // g] = 1
	print()
for _ in range(ii()):
	solve()


import sys
import math
import heapq

def input():
	return sys.stdin.readline().strip('\n')

def I():
	return input()

def II():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def isPerfectSquare(x):
	return int(math.sqrt(x)) ** 2 == x
for _ in range(II()):
	n = II()
	s = I()
	d = {}
	(countD, countK) = (0, 0)
	for i in range(n):
		if s[i] == 'D':
			countD += 1
		if s[i] == 'K':
			countK += 1
		(p, q) = (countD, countK)
		g = math.gcd(countD, countK)
		(p, q) = (p / g, q / g)
		if (p, q) not in d:
			d[p, q] = 1
		else:
			d[p, q] += 1
		print(d[p, q], end=' ')
	print()


import os
import sys
from io import BytesIO, IOBase
import math
from queue import Queue
import collections
import itertools
import bisect
import heapq
import random

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(int(n))
	return l

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def maxPrimeFactors(n):
	maxPrime = -1
	while n % 2 == 0:
		maxPrime = 2
		n >>= 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			maxPrime = i
			n = n / i
	if n > 2:
		maxPrime = n
	return int(maxPrime)

def countcon(s, i):
	c = 0
	ch = s[i]
	for i in range(i, len(s)):
		if s[i] == ch:
			c += 1
		else:
			break
	return c

def lis(arr):
	n = len(arr)
	lis = [1] * n
	for i in range(1, n):
		for j in range(0, i):
			if arr[i] > arr[j] and lis[i] < lis[j] + 1:
				lis[i] = lis[j] + 1
	maximum = 0
	for i in range(n):
		maximum = max(maximum, lis[i])
	return maximum

def isSubSequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def maxfac(n):
	root = int(n ** 0.5)
	for i in range(2, root + 1):
		if n % i == 0:
			return n // i
	return n

def p2(n):
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	return c

def seive(n):
	primes = [True] * (n + 1)
	primes[1] = primes[0] = False
	i = 2
	while i * i <= n:
		if primes[i] == True:
			for j in range(i * i, n + 1, i):
				primes[j] = False
		i += 1
	pr = []
	for i in range(0, n + 1):
		if primes[i]:
			pr.append(i)
	return pr

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def denofactinverse(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return pow(fac, m - 2, m)

def numofact(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return fac

def sod(n):
	s = 0
	while n > 0:
		s += n % 10
		n //= 10
	return s
for xyz in range(0, int(input())):
	n = int(input())
	s = input()
	d = {}
	dc = kc = 0
	for i in range(0, n):
		if s[i] == 'D':
			dc += 1
		else:
			kc += 1
		gc = math.gcd(dc, kc)
		(td, tk) = (dc // gc, kc // gc)
		if (td, tk) in d:
			d[td, tk] += 1
		else:
			d[td, tk] = 1
		print(d[td, tk], end=' ')
	print('')


def main():
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
	inf = 1e+17
	mod = 10 ** 9 + 7

	def factorial(n):
		f = 1
		for i in range(1, n + 1):
			f = f * i % mod
		return f

	def ncr(n, r):
		num = den = 1
		for i in range(r):
			num = num * (n - i) % mod
			den = den * (i + 1) % mod
		return num * pow(den, mod - 2, mod) % mod

	def solve(n, arr):
		cnt = dict()
		ds = 0
		ks = 0
		answer = []
		for i in range(n):
			if arr[i] == 'D':
				ds += 1
			else:
				ks += 1
			if ks:
				if ds / ks in cnt:
					cnt[ds / ks] += 1
				else:
					cnt[ds / ks] = 1
				answer.append(cnt[ds / ks])
			else:
				if inf in cnt:
					cnt[inf] += 1
				else:
					cnt[inf] = 1
				answer.append(cnt[inf])
		return ' '.join(list(map(str, answer)))
		pass
	t = int(input())
	ans = []
	for _ in range(t):
		n = int(input())
		arr = list(input())[:-1]
		ans.append(solve(n, arr))
	for answer in ans:
		print(answer)
import sys, threading
import bisect
import math
import itertools
from sys import stdout
import heapq
from queue import PriorityQueue
input = sys.stdin.readline
thread = threading.Thread(target=main)
thread.start()
thread.join()


from collections import defaultdict
from math import gcd
for _ in range(int(input())):
	n = int(input())
	s = input()
	D = [0] * n
	K = [0] * n
	if s[0] == 'D':
		D[0] = 1
	else:
		K[0] = 1
	for i in range(1, n):
		if s[i] == 'D':
			D[i] = D[i - 1] + 1
			K[i] = K[i - 1]
		else:
			K[i] = K[i - 1] + 1
			D[i] = D[i - 1]
	ans = [1] * n
	rat = defaultdict(int)
	for i in range(n):
		if K[i] == 0:
			rat[0] += 1
			ans[i] = rat[0]
		elif D[i] == 0:
			rat[0] += 1
			ans[i] = rat[0]
		elif K[i] > D[i]:
			x = gcd(K[i], D[i])
			up = K[i] / x
			down = D[i] / x
			ans[i] += rat[up, down, 0]
			rat[up, down, 0] += 1
		elif K[i] == D[i]:
			ans[i] += rat[1]
			rat[1] += 1
		else:
			x = gcd(D[i], K[i])
			up = D[i] / x
			down = K[i] / x
			ans[i] += rat[up, down]
			rat[up, down] += 1
	print(*ans)


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
from math import gcd
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def scanf(datatype=str):
	return datatype(sys.stdin.readline().rstrip())

def printf(answer=''):
	return sys.stdout.write(str(answer) + '\n')

def prints(answer):
	return sys.stdout.write(str(answer) + ' ')

def map_input(datatype=str):
	return map(datatype, sys.stdin.readline().split())

def list_input(datatype=str):
	return list(map(datatype, sys.stdin.readline().split()))

def testcase(number: int, solve_function):
	for _ in range(number):
		solve_function()

def solve():
	n = scanf(int)
	s = scanf()
	hashMap = Counter()
	d = k = 0
	for i in range(n):
		if s[i] == 'D':
			d += 1
		else:
			k += 1
		D = d / gcd(d, k)
		K = k / gcd(d, k)
		hashMap[D, K] += 1
		prints(hashMap[D, K])
	printf()
t = scanf(int)
testcase(t, solve)


for _ in range(int(input())):
	n = int(input())
	st = input()
	count = 0
	sum_arr = [0]
	for i in range(n):
		if st[i] == 'D':
			count += 1
		sum_arr.append(count)
	ans = [1 for i in range(n + 1)]
	i = 1
	d = {}
	while i <= n:
		if sum_arr[i] == i:
			value = d.get(-1, 1)
			ans[i] = max(ans[i], value)
			d[-1] = value + 1
			i += 1
			continue
		value = d.get(sum_arr[i] / (i - sum_arr[i]), 1)
		ans[i] = max(ans[i], value)
		d[sum_arr[i] / (i - sum_arr[i])] = value + 1
		i += 1
	print(*ans[1:])


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = []
	dic = {}
	d = 0
	k = 0
	for i in s:
		if i == 'D':
			d += 1
		else:
			k += 1
		if k == 0:
			if dic.get(-1, -1) == -1:
				dic[-1] = 1
			else:
				dic[-1] += 1
			ans.append(dic[-1])
		else:
			if dic.get(d / k, -1) == -1:
				dic[d / k] = 1
			else:
				dic[d / k] += 1
			ans.append(dic[d / k])
	print(*ans)


from collections import defaultdict

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	s = input()
	(d, k) = (0, 0)
	ans = []
	t = defaultdict(int)
	for i in s:
		if i == 'D':
			d += 1
		else:
			k += 1
		gc = gcd(d, k)
		t[d // gc, k // gc] += 1
		ans.append(t[d // gc, k // gc])
	print(' '.join(map(str, ans)))


import math
t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	map = {}
	dc = 0
	kc = 0
	ans = [1 for x in range(n)]
	for i in range(n):
		if s[i] == 'D':
			dc += 1
		else:
			kc += 1
		if kc == 0:
			if (0, 0) not in map:
				map[0, 0] = 1
			else:
				map[0, 0] += 1
			ans[i] = map[0, 0]
		else:
			d = math.gcd(dc, kc)
			(a, b) = (dc // d, kc // d)
			if (a, b) not in map:
				map[a, b] = 1
			else:
				map[a, b] += 1
			ans[i] = map[a, b]
	print(*ans)


from sys import *
from collections import defaultdict as dd
from math import *
from bisect import *

def sinp():
	return input()

def inp():
	return int(sinp())

def minp():
	return map(int, sinp().split())

def linp():
	return list(minp())

def strl():
	return list(sinp())

def pr(x):
	print(x)
mod = int(1000000000.0 + 7)
for _ in range(inp()):
	n = inp()
	s = sinp()
	d = dd(int)
	d[-1, -1] = 0
	(x, y) = (0, 0)
	res = []
	for i in range(n):
		if s[i] == 'D':
			x += 1
		if s[i] == 'K':
			y += 1
		t = (x // gcd(x, y), y // gcd(x, y))
		if t in d:
			res.append(d[t] + 1)
		else:
			res.append(1)
		d[t] = d.get(t, 0) + 1
	print(*res)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	s = list(input())
	ans = []
	dic = {}
	count1 = 0
	count2 = 0
	for i in range(n):
		count1 += int(s[i] == 'D')
		count2 += int(s[i] == 'K')
		a = count1 // gcd(count1, count2)
		b = count2 // gcd(count1, count2)
		if (a, b) not in dic:
			dic[a, b] = 1
		else:
			dic[a, b] += 1
		ans.append(dic[a, b])
	print(*ans)


import os
import sys
from io import BytesIO, IOBase
from math import ceil, floor, pow, sqrt, gcd
from collections import Counter, defaultdict
from itertools import permutations, combinations
from time import time, sleep
BUFSIZE = 8192
MOD = 1000000007

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from os import path
if path.exists('tc.txt'):
	stdin = open('tc.txt', 'r')

def gmi():
	return map(int, stdin.readline().strip().split())

def gms():
	return map(str, stdin.readline().strip().split())

def gari():
	return list(map(int, stdin.readline().strip().split()))

def gart():
	return tuple(map(int, stdin.readline().strip().split()))

def gars():
	return list(map(str, stdin.readline().strip().split()))

def gs():
	return stdin.readline().strip()

def gls():
	return list(stdin.readline().strip())

def gi():
	return int(stdin.readline())

def pri(i):
	stdout.write(f'{i}\n')

def priar(ar):
	stdout.write(' '.join(map(str, ar)) + '\n')

def prist(s):
	stdout.write(''.join(map(str, s)) + '\n')
dct = defaultdict(int)
tc = gi()
while tc:
	tc -= 1
	n = gi()
	s = gs()
	(d, k) = (0, 0)
	dct.clear()
	for i in s:
		if i == 'D':
			d += 1
		else:
			k += 1
		g = gcd(d, k)
		(rd, rk) = (d // g, k // g)
		dct[rd, rk] += 1
		stdout.write(str(dct[rd, rk]) + ' ')
	stdout.write('\n')


def HCF(a, b):
	if a < b:
		return HCF(b, a)
	elif a == b:
		return a
	elif b == 0:
		return a
	else:
		return HCF(b, a % b)

def red(numD, numK):
	if numD == 0:
		return (0, 1)
	elif numK == 0:
		return (1, 0)
	else:
		factor = HCF(numD, numK)
		return (numD // factor, numK // factor)
t = int(input())
for i in range(t):
	k = int(input())
	arr = input()[:k]
	dic = {}
	numD = 0
	numK = 0
	ans = []
	for a in arr:
		if a == 'D':
			numD += 1
		else:
			numK += 1
		(nd, nk) = red(numD, numK)
		if nd not in dic:
			ans.append('1')
			dic[nd] = {}
			dic[nd][nk] = 1
		elif nk not in dic[nd]:
			ans.append('1')
			dic[nd][nk] = 1
		else:
			dic[nd][nk] += 1
			ans.append(str(dic[nd][nk]))
	print(' '.join(ans))


import sys
import math
from collections import defaultdict
T = int(input())
for t in range(T):
	N = int(input())
	S = input()
	cnt = defaultdict(int)
	ans = []
	countD = countK = 0
	for (index, char) in enumerate(S):
		countD += char == 'D'
		countK += char == 'K'
		gcd = math.gcd(countK, countD)
		key = (countK // gcd, countD // gcd)
		cnt[key] += 1
		ans.append(cnt.get(key, 1))
	print(' '.join(map(str, ans)))


import math

def solve(s):
	store = {}
	last_ds = 0
	last_ks = 0
	result = []
	for i in range(len(s)):
		last_ds = ds = last_ds + (1 if s[i] == 'D' else 0)
		last_ks = ks = last_ks + (1 if s[i] == 'K' else 0)
		g = math.gcd(ds, ks)
		(ds, ks) = (ds // g, ks // g)
		if (ds, ks) in store:
			store[ds, ks] += 1
			result.append(store[ds, ks])
		else:
			store[ds, ks] = 1
			result.append(1)
	return result
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	result = solve(s)
	for e in result:
		print(e, end=' ')
	print()
pass


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	s = str(input())
	d = defaultdict(int)
	dd = 0
	k = 0
	for i in s:
		if i == 'D':
			dd += 1
		else:
			k += 1
		q = math.gcd(dd, k)
		c = dd // q
		cc = k // q
		ss = f'{c}:{cc}'
		d[ss] += 1
		print(d[ss], end=' ')
	print()


from math import gcd
for testis in range(int(input())):
	n = int(input())
	s = input()
	d = {}
	cd = ck = 0
	for x in s:
		if x == 'D':
			cd += 1
		else:
			ck += 1
		a = (cd / gcd(cd, ck), ck / gcd(cd, ck))
		if a in d:
			d[a] += 1
		else:
			d[a] = 1
		print(d[a])


from itertools import accumulate as ac
from collections import Counter as cc
from bisect import bisect_left as bsl
from bisect import bisect as bs
from math import factorial as f
from collections import *
from itertools import *
from string import *
from bisect import *
from queue import *
from heapq import *
from math import *
from sys import *
from re import *

def fast():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in fast().split()]
(z, zz) = (input, lambda : list(map(int, z().split())))
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def output(answer):
	stdout.write(str(answer))
num = int(input())
for _ in range(num):
	n = int(input())
	arr = input()
	s = {}
	(d, k) = (0, 0)
	for i in arr:
		if i == 'D':
			d += 1
		else:
			k += 1
		g = gcd(d, k)
		try:
			s[d // g, k // g] += 1
		except:
			s[d // g, k // g] = 1
		print(s[d // g, k // g], end=' ')
	print()


import math
for _ in range(int(input())):
	n = int(input())
	a = input()
	ks = [0]
	ds = [0]
	for i in range(n):
		if a[i] == 'K':
			ks.append(ks[-1] + 1)
			ds.append(ds[-1])
		else:
			ds.append(ds[-1] + 1)
			ks.append(ks[-1])
	dec = {}
	res = []
	for i in range(n):
		p = ks[i + 1]
		q = ds[i + 1]
		if p == 0:
			res.append(q)
		elif q == 0:
			res.append(p)
		else:
			mm = math.gcd(p, q)
			p = p // mm
			q = q // mm
			key = '{}|{}'.format(p, q)
			if key in dec:
				res.append(dec[key] + 1)
				dec[key] += 1
			else:
				dec[key] = 1
				res.append(1)
	print(*res)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	arr = input()
	(a, b) = (0, 0)
	d = {}
	res = [1 for i in range(n)]
	for i in range(n):
		if arr[i] == 'D':
			a += 1
		else:
			b += 1
		(aa, bb) = (a, b)
		curr = gcd(aa, bb)
		while curr > 1:
			aa = aa // curr
			bb = bb // curr
			curr = gcd(aa, bb)
		d[aa, bb] = d.get((aa, bb), 0) + 1
		if d[aa, bb] > 1:
			res[i] = d[aa, bb]
	print(*res)


import sys
input = sys.stdin.readline
from math import gcd
for _ in range(int(input())):
	n = int(input())
	s = input()[:-1]
	seen = {}
	(x, y) = (0, 0)
	ans = []
	for (i, c) in enumerate(s):
		if c == 'D':
			x += 1
		else:
			y += 1
		g = gcd(x, y)
		x0 = x // g
		y0 = y // g
		if (x0, y0) not in seen:
			seen[x0, y0] = 1
			ans.append(1)
		else:
			seen[x0, y0] += 1
			ans.append(seen[x0, y0])
	print(*ans)


import sys
import math
import heapq
import bisect
from collections import Counter
from collections import defaultdict
from io import BytesIO, IOBase
import string
import fractions

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None
		self.BUFSIZE = 8192

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
	return int(input())

def get_ints():
	return list(map(int, input().split(' ')))

def get_int_grid(n):
	return [get_ints() for _ in range(n)]

def get_str():
	return input().strip()

def get_strs():
	return get_str().split(' ')

def flat_list(arr):
	return [item for subarr in arr for item in subarr]

def yes_no(b):
	if b:
		return 'YES'
	else:
		return 'NO'

def binary_search(good, left, right, delta=1, right_true=False):
	limits = [left, right]
	while limits[1] - limits[0] > delta:
		if delta == 1:
			mid = sum(limits) // 2
		else:
			mid = sum(limits) / 2
		if good(mid):
			limits[int(right_true)] = mid
		else:
			limits[int(~right_true)] = mid
	if good(limits[int(right_true)]):
		return limits[int(right_true)]
	else:
		return False

def prefix_sums(a):
	p = [0]
	for x in a:
		p.append(p[-1] + x)
	return p

def solve_a():
	n = get_int()
	a = get_ints()
	g = 0
	for x in a:
		g = math.gcd(g, x)
	if min(a) < 0:
		return False
	else:
		return list(range(max(a) + 1))

def solve_b():
	n = get_int()
	s = get_str()
	alpha = list(string.ascii_lowercase)
	for x in alpha:
		if x not in s:
			return x
	for i in range(26):
		for j in range(26):
			(x, y) = (alpha[i], alpha[j])
			if x + y not in s:
				return x + y
	for i in range(26):
		for j in range(26):
			for k in range(26):
				(x, y, z) = (alpha[i], alpha[j], alpha[k])
				if x + y + z not in s:
					return x + y + z
	return False

def solve_c():
	ratios = defaultdict(int)
	n = get_int()
	s = list(get_str())
	(d, k) = (0, 0)
	ans = []
	for x in s:
		if x == 'D':
			d += 1
		else:
			k += 1
		g = math.gcd(d, k)
		f = (d // g, k // g)
		ratios[f] += 1
		ans.append(ratios[f])
	return ans
t = get_int()
for _ in range(t):
	print(*solve_c())


from sys import stdin
import math
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	s = stdin.readline()[:-1]
	(d, k) = (0, 0)
	freq = {}
	for i in s:
		if i == 'D':
			d += 1
		else:
			k += 1
		(x, y) = (d, k)
		g = math.gcd(x, y)
		f = (x // g, y // g)
		if f not in freq:
			freq[f] = 0
		freq[f] += 1
		print(freq[f], end=' ')
	print()


import math
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	s = input()
	d = 0
	k = 0
	l = []
	c = defaultdict(int)
	for i in range(n):
		if s[i] == 'D':
			d += 1
		else:
			k += 1
		if k == 0 or d == 0:
			l.append(max(k, d))
		else:
			m = d
			n = k
			g = math.gcd(d, k)
			m = m // g
			n = n // g
			c[m, n] += 1
			l.append(c[m, n])
	print(*l)


from math import gcd
from collections import defaultdict

def solve(s):
	d_count = k_count = 0
	counts = defaultdict(lambda : 0)
	soln = []
	for c in s:
		if c == 'D':
			d_count += 1
		else:
			k_count += 1
		g = gcd(d_count, k_count)
		pair = (d_count // g, k_count // g)
		counts[pair] += 1
		soln.append(str(counts[pair]))
	return soln

def main():
	t = int(input())
	for _ in range(t):
		input()
		s = input().strip()
		print(' '.join(solve(s)))
main()


import sys
import math
import collections
from math import gcd
inp = lambda : int(input())
strng = lambda : input().strip()
strl = lambda : list(input().strip())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
mod = 10 ** 9 + 7
input = sys.stdin.readline
t = inp()
for t1 in range(t):
	n = inp()
	s = strng()
	d = {}
	D = 0
	K = 0
	ans = []
	for i in range(n):
		if s[i] == 'D':
			D += 1
		else:
			K += 1
		if K == 0:
			temp = str(1) + ' ' + str(0)
			d[temp] = d.get(temp, 0) + 1
			ans.append(str(d[temp]))
		elif D == 0:
			temp = str(0) + ' ' + str(1)
			d[temp] = d.get(temp, 0) + 1
			ans.append(str(d[temp]))
		else:
			g = gcd(D, K)
			temp = str(D // g) + ' ' + str(K // g)
			d[temp] = d.get(temp, 0) + 1
			ans.append(str(d[temp]))
	print(' '.join(ans), flush=True)


import sys
import collections
import math
inf = sys.maxsize

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 1000000007
for _ in range(int(input())):
	n = int(input())
	s = input()
	mp = collections.defaultdict(int)
	countD = countK = 0
	for i in range(n):
		if s[i] == 'D':
			countD += 1
		else:
			countK += 1
		gcd = math.gcd(countD, countK)
		a = countD // gcd
		b = countK // gcd
		print(mp[a, b] + 1, end=' ')
		mp[a, b] += 1
	print()


import math
for z in range(int(input())):
	n = int(input())
	ans = {}
	d = k = 0
	l = []
	for i in input():
		if i == 'D':
			d += 1
		else:
			k += 1
		z = math.gcd(d, k)
		(x, y) = (d // z, k // z)
		cur = ans.get((x, y), 0) + 1
		l.append(cur)
		ans[x, y] = cur
	print(*l)


import math
from collections import defaultdict

def simplify(a, b):
	p = math.gcd(a, b)
	return (a // p, b // p)

def solve(s):
	ans = []
	ratios = defaultdict(int)
	(a, b) = (0, 0)
	for si in s:
		if si == 'K':
			a += 1
		else:
			b += 1
		p = simplify(a, b)
		ans.append(ratios[p] + 1)
		ratios[p] += 1
	print(*ans)
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	solve(s)


from sys import stdin, stdout

def arrin():
	return list(map(int, stdin.readline().split()))

def num1in():
	return int(stdin.readline())

def num2in():
	(a, b) = map(int, stdin.readline().split())
	return (a, b)

def num3in():
	(a, b, c) = map(int, stdin.readline().split())
	return (a, b, c)

def num4in():
	(a, b, c, d) = map(int, stdin.readline().split())
	return (a, b, c, d)

def num5in():
	(a, b, c, d, e) = map(int, stdin.readline().split())
	return (a, b, c, d, e)
t = num1in()
for test in range(t):
	n = num1in()
	s = input()
	dict = {}
	ans = []
	d = 0
	k = 0
	prev = 0
	for i in s:
		if i == 'D':
			d += 1
		else:
			k += 1
		if d == 0 or k == 0:
			prev += 1
			ans.append(prev)
		else:
			ratio = d / k
			if ratio in dict:
				temp = dict[ratio] + 1
				dict[ratio] = temp
				ans.append(temp)
			else:
				temp = 1
				dict[ratio] = temp
				ans.append(temp)
	for i in ans:
		print(i, end=' ')
	print()


from collections import defaultdict as di

def solve(s):
	d = di(int)
	a = []
	d['K'] = 0
	d['D'] = 0
	for i in s:
		z = []
		d[i] += 1
		a.append([d['D'], d['K']])
	ans = [1] * len(a)
	d = {}
	for i in range(len(a)):
		if a[i][1] == 0:
			ratio = -1
		else:
			ratio = a[i][0] / a[i][1]
		if ratio in d:
			ans[i] = ans[d[ratio]] + 1
		d[ratio] = i
	return ans
for _ in range(int(input())):
	n = int(input())
	a = list(input())
	ans = solve(a)
	print(*ans)


import math, sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, s) = (int(input()), input().strip())
	(d_f, k_f, cnt, ans) = (0, 0, {}, 0)
	for i in range(n):
		if s[i] == 'D':
			d_f += 1
		else:
			k_f += 1
		(loc_d_f, loc_k_f) = (d_f // math.gcd(d_f, k_f), k_f // math.gcd(d_f, k_f))
		cnt[loc_d_f, loc_k_f] = cnt.get((loc_d_f, loc_k_f), 0) + 1
		print(cnt[loc_d_f, loc_k_f], end=' ')
	print('')


import math
a = []
for s in [*open(0)][2::2]:
	D = {}
	d = k = 0
	for c in s[:-1]:
		if c < 'K':
			d += 1
		else:
			k += 1
		g = math.gcd(d, k)
		l = (d / g, k / g)
		D[l] = D.get(l, 0) + 1
		a += (D[l],)
print(*a)


import sys
import io, os
input = sys.stdin.readline
from itertools import accumulate
from collections import defaultdict
import math
t = int(input())
for _ in range(t):
	n = int(input())
	s = str(input().rstrip())
	D = [0] * n
	K = [0] * n
	for (i, c) in enumerate(s):
		if c == 'D':
			D[i] += 1
		else:
			K[i] += 1
	D = list(accumulate(D))
	K = list(accumulate(K))
	ans = [0] * n
	d = defaultdict(lambda : 0)
	for i in range(n):
		g = math.gcd(D[i], K[i])
		(x, y) = (D[i] // g, K[i] // g)
		ans[i] = d[x, y] + 1
		d[x, y] += 1
	print(*ans)


from math import *
import sys
from itertools import product
from string import ascii_lowercase
k1 = [''.join(i) for i in product(ascii_lowercase, repeat=1)]
k2 = [''.join(i) for i in product(ascii_lowercase, repeat=2)]
k3 = [''.join(i) for i in product(ascii_lowercase, repeat=3)]
k = k1 + k2 + k3
input = sys.stdin.readline
sys.setrecursionlimit(3 * 10 ** 5)

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	n = inp()
	t -= 1
	s = st()
	z = {}
	(d, k) = (0, 0)
	for i in s:
		if i == 'D':
			d += 1
		else:
			k += 1
		z1 = gcd(d, k)
		try:
			z[d // z1, k // z1] += 1
		except:
			z[d // z1, k // z1] = 1
		print(z[d // z1, k // z1], end=' ')
	print()


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
from math import gcd
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
MOD = 10 ** 9 + 7
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	for _ in range(int(input())):
		n = int(input())
		a = input()
		dic = {}
		(d, k) = (0, 0)
		for i in range(n):
			if a[i] == 'D':
				d += 1
			else:
				k += 1
			x = gcd(d, k)
			d //= x
			k //= x
			dic[d, k] = dic.get((d, k), 0) + 1
			print(dic[d, k], end=' ')
			d *= x
			k *= x
		print()
main()


from math import gcd
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	cnt = [0, 0]
	freq = {}
	ans = [0] * n
	for (i, x) in enumerate(s):
		x = 1 if x == s[0] else 0
		cnt[x] += 1
		g = gcd(*cnt)
		f = cnt[0] // g / (cnt[1] // g)
		ans[i] = freq[f] = freq.get(f, 0) + 1
	print(*ans)


import math
for _ in range(int(input())):
	n = int(input())
	string = input()
	ratios = dict()
	D = 0
	K = 0
	ans = []
	for i in range(n):
		if string[i] == 'D':
			D += 1
		else:
			K += 1
		if D == 0:
			ratio = (1, 0)
		elif K == 0:
			ratio = (0, 1)
		else:
			g = math.gcd(D, K)
			ratio = (D // g, K // g)
		ratios[ratio] = ratios.get(ratio, 0) + 1
		ans.append(ratios[ratio])
	print(*ans)


from sys import stdin as sin

def aint():
	return int(input())

def amap():
	return map(int, sin.readline().split())

def alist():
	return list(map(int, sin.readline().split()))

def astr():
	return input()
from math import gcd
for _ in range(aint()):
	n = aint()
	s = input()
	l = list(s)
	a = [0] * n
	b = [0] * n
	if l[0] == 'D':
		a[0] += 1
	else:
		b[0] += 1
	for i in range(1, n):
		if l[i] == 'D':
			a[i] += 1
		else:
			b[i] += 1
		a[i] += a[i - 1]
		b[i] += b[i - 1]
	d = {}
	for i in range(n):
		if a[i] == 0 or b[i] == 0:
			print(i + 1, end=' ')
		else:
			if d.get(a[i] / b[i], None) == None:
				d[a[i] / b[i]] = 0
				print(1, end=' ')
			else:
				print(d.get(a[i] / b[i]) + 1, end=' ')
			d[a[i] / b[i]] += 1
	print()


from math import ceil, floor, gcd, sqrt, log2
from collections import Counter
from copy import deepcopy
from string import ascii_lowercase
alpha = ascii_lowercase
for ttt in range(int(input())):
	n = int(input())
	s = input()
	d_count = 0
	k_count = 0
	d = {}
	for i in range(n):
		if s[i] == 'D':
			d_count += 1
		else:
			k_count += 1
		gc = gcd(d_count, k_count)
		lst = [d_count // gc, k_count // gc]
		lst = str(lst)
		if lst not in d:
			d[lst] = 1
		else:
			d[lst] += 1
		print(d[lst], end=' ')
	print()


import math
for s in [*open(0)][2::2]:
	D = {}
	d = i = 0
	for c in s[:-1]:
		if c < 'K':
			d += 1
		i += 1
		g = math.gcd(d, i)
		l = (d / g, (i - d) / g)
		D[l] = D.get(l, 0) + 1
		print(D[l], end=' ')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	p = {}
	d = 0
	k = 0
	ans = []
	flag = 0
	for i in range(n):
		x = s[i]
		if x == 'D':
			d += 1
		else:
			k += 1
		if d > 0 and k > 0:
			flag = 1
		if flag == 0:
			ans.append(i + 1)
			continue
		e = d / k
		if e in p:
			p[e] += 1
		else:
			p[e] = 1
		ans.append(p[e])
	print(*ans)


import os
import sys
from io import BytesIO, IOBase
import math
from collections import Counter
DIV = {}

def printDivisors(n):
	all_div = set()
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n == i * i:
				all_div.add(i)
			else:
				all_div.add(i)
				all_div.add(n // i)
		i = i + 1
	return sorted(all_div, reverse=True)

def func(n, array):
	D = 0
	K = 0
	result = []
	ratios = {}
	for val in array:
		if val == 'D':
			D += 1
		else:
			K += 1
		if D == 0 or K == 0:
			result.append(max(D, K))
		else:
			val = math.gcd(D, K)
			min_D = D // val
			min_K = K // val
			if (min_D, min_K) in ratios:
				ratios[min_D, min_K] += 1
			else:
				ratios[min_D, min_K] = 1
			result.append(ratios[min_D, min_K])
	return ' '.join(map(str, result))

def main():
	num_test = int(parse_input())
	result = []
	for _ in range(num_test):
		n = int(parse_input())
		array = parse_input()
		result.append(func(n, array))
	print('\n'.join(map(str, result)))
parse_input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math

def solve(word):
	last_ratio_index = {}
	ratiod = 0
	ratiok = 0
	res = []
	sol_cache = [1] * len(word)
	for i in range(len(word)):
		if word[i] == 'D':
			ratiod += 1
		else:
			ratiok += 1
		gcd_dk = math.gcd(ratiod, ratiok)
		ratiod_min = ratiod // gcd_dk
		ratiok_min = ratiok // gcd_dk
		ratio = (ratiod_min, ratiok_min)
		if ratiok_min == 0:
			ratio = (1, 0)
		if ratiod_min == 0:
			ratio = (0, 1)
		if ratio in last_ratio_index:
			this_sol = sol_cache[last_ratio_index[ratio]] + 1
			res.append(this_sol)
		else:
			this_sol = 1
		sol_cache[i] = this_sol
		last_ratio_index[ratio] = i
	return [str(x) for x in sol_cache]
cache = {}
T = int(input())
for t in range(T):
	N = int(input())
	word = input()
	res = solve(word)
	print(' '.join(res), flush=True)


from math import *
for _ in range(int(input())):
	n = int(input())
	s = input()
	d = 0
	k = 0
	ans = [0] * n
	dict = {}
	for i in range(n):
		if s[i] == 'D':
			d += 1
		else:
			k += 1
		if gcd(d, k) == 1:
			dict[str(d) + ' ' + str(k)] = 1
			ans[i] = 1
		else:
			g = gcd(d, k)
			if str(d // g) + ' ' + str(k // g) in dict:
				ans[i] = dict[str(d // g) + ' ' + str(k // g)] + 1
				dict[str(d) + ' ' + str(k)] = ans[i]
				dict[str(d // g) + ' ' + str(k // g)] += 1
			else:
				ans[i] = 1
				dict[str(d // g) + ' ' + str(k // g)] = 1
	print(*ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def gcd(a, b):
	if not b:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	s = input()
	x = {}
	(d, k) = (0, 0)
	for i in range(n):
		if s[i] == 'D':
			d += 1
		else:
			k += 1
		g = gcd(d, k)
		t = (d // g, k // g)
		x[t] = x.get(t, 0) + 1
		print(x[t], end=' ')
	print()


import math
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	s = str(input())
	d = defaultdict(int)
	dd = 0
	k = 0
	for i in s:
		if i == 'D':
			dd += 1
		else:
			k += 1
		q = math.gcd(dd, k)
		c = dd // q
		cc = k // q
		ss = f'{c}:{cc}'
		d[ss] += 1
		print(d[ss], end=' ')
	print()


T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	from math import gcd
	dct = 0
	kct = 0
	seen = dict()
	for i in s:
		if i == 'D':
			dct += 1
		else:
			kct += 1
		cur = tuple([dct // gcd(dct, kct), kct // gcd(dct, kct)])
		if cur not in seen:
			seen[cur] = 1
		else:
			seen[cur] += 1
		print(seen[cur], end=' ')
	print()


from collections import defaultdict

def read_int():
	return int(input())

def read_ints():
	return map(int, input().split(' '))

def gcd(x, y):
	return x if y == 0 else gcd(y, x % y)
t = read_int()
for case_num in range(t):
	n = read_int()
	s = input()
	d = defaultdict(int)
	cd = 0
	ck = 0
	ans = []
	for c in s:
		if c == 'D':
			cd += 1
		else:
			ck += 1
		g = gcd(cd, ck)
		d[cd // g, ck // g] += 1
		ans.append(d[cd // g, ck // g])
	print(' '.join(map(str, ans)))


for _ in range(int(input())):
	n = int(input())
	s = input()
	countd = 0
	countk = 0
	(d, k) = ([0] * n, [0] * n)
	dk = [-1] * n
	ans = [-1] * n
	dic = dict()
	dic[-1] = 0
	for i in range(n):
		if s[i] == 'D':
			countd += 1
		else:
			countk += 1
		d[i] = countd
		k[i] = countk
		if d[i] and k[i]:
			dk[i] = countd / countk
			if dk[i] in dic:
				dic[dk[i]] += 1
			else:
				dic[dk[i]] = 1
		else:
			dic[-1] += 1
		ans[i] = dic[dk[i]]
	print(*ans)


import math
for i in range(int(input())):
	n = int(input())
	s = input()
	d1 = {}
	d = 0
	k = 0
	for i in s:
		if i == 'D':
			d += 1
		else:
			k += 1
		x = math.gcd(d, k)
		d2 = d // x
		k1 = k // x
		z = (d2, k1)
		if z not in d1:
			print(1, end=' ')
			d1[z] = d1.get(z, 0) + 1
		else:
			d1[z] += 1
			print(d1[z], end=' ')
	print()


import sys, heapq, math
from collections import defaultdict, deque
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	s = input()
	(cnt1, cnt2) = (0, 0)
	H = defaultdict(list)
	for i in range(n):
		if s[i] == 'D':
			cnt1 += 1
		else:
			cnt2 += 1
		v = math.gcd(cnt1, cnt2)
		H[cnt1 // v, cnt2 // v].append(i)
	ans = [1] * n
	for v in H:
		arr = H[v]
		for i in range(len(arr)):
			ans[arr[i]] = i + 1
	print(*ans)


from itertools import chain

def gcd(a, b):
	if a < b:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(a % b, b)

def solve():
	n = int(input())
	s = input()
	a = [0] * n
	map_ = dict()
	for i in range(n):
		if s[i] == 'D':
			if not i:
				a[i] = 1
			else:
				a[i] = a[i - 1] + 1
		elif i:
			a[i] = a[i - 1]
		else:
			a[i] = 0
		d = gcd(a[i], i + 1 - a[i])
		map_[a[i] // d, (i + 1 - a[i]) // d] = map_.get((a[i] // d, (i + 1 - a[i]) // d), 0) + 1
		print(map_[a[i] // d, (i + 1 - a[i]) // d], end=' ')
	print()
for t in range(int(input())):
	solve()


from math import *
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	b = {}
	nD = 0
	nK = 0
	for i in range(len(s)):
		if s[i] == 'D':
			nD += 1
		elif s[i] == 'K':
			nK += 1
		x = nD // gcd(nD, nK)
		y = nK // gcd(nD, nK)
		if (x, y) in b.keys():
			b[x, y] += 1
		else:
			b[x, y] = 1
		print(b[x, y], end=' ')
	print()


def same(x, y):
	return x[0] * y[1] == y[0] * x[1]
from collections import defaultdict
import math

def solve():
	n = int(input())
	s = input()
	ans = [1 for i in range(n)]
	d_count = [0 for i in range(n)]
	d_count[0] = s[0] == 'D'
	for i in range(n):
		d_count[i] = d_count[i - 1] + (s[i] == 'D')
	prev = defaultdict(lambda : 0)
	for ind in range(n):
		(x, y) = [d_count[ind], ind + 1 - d_count[ind]]
		g = math.gcd(x, y)
		x //= g
		y //= g
		if x > 0 and y > 0:
			prev[x, y] = prev[x, y] + 1
			ans[ind] = prev[x, y]
		elif x == 0:
			prev[0, 1] = prev[0, 1] + 1
			ans[ind] = prev[0, 1]
		else:
			prev[1, 0] = prev[1, 0] + 1
			ans[ind] = prev[1, 0]
	print(*ans)

def main():
	for case in range(int(input())):
		solve()
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin, stdout, setrecursionlimit as srl
from threading import stack_size
from collections import deque, defaultdict as dd
from math import gcd, ceil
input = stdin.readline
flush = stdout.flush
tc = 1
tc = int(input())
for _ in range(tc):
	n = int(input())
	s = input()
	d = [1 * (s[0] == 'D') for i in range(n)]
	k = [1 * (s[0] == 'K') for i in range(n)]
	for i in range(1, n):
		if s[i] == 'D':
			d[i] = d[i - 1] + 1
			k[i] = k[i - 1]
		else:
			d[i] = d[i - 1]
			k[i] = k[i - 1] + 1
	c = dd(lambda : 0)
	ans = [1 for i in range(n)]
	for i in range(n):
		if d[i] == 0:
			ans[i] += c[0, 1]
			c[0, 1] += 1
		elif k[i] == 0:
			ans[i] += c[1, 0]
			c[1, 0] += 1
		else:
			g = gcd(d[i], k[i])
			ans[i] += c[d[i] // g, k[i] // g]
			c[d[i] // g, k[i] // g] += 1
	print(*ans)


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2
prime = [True for i in range(10)]
pp = [0] * 10

def SieveOfEratosthenes(n=10):
	p = 2
	c = 0
	while p * p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				pp[i] += 1
				prime[i] = False
		p += 1

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[n - 1]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = arr[mid]
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[0]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = arr[mid]
			left = mid + 1
	return res
t = 1
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(d, k) = (0, 0)
	dd = defaultdict(int)
	res = []
	for i in s:
		if i == 'D':
			d += 1
		else:
			k += 1
		g = math.gcd(d, k)
		(nd, nk) = (d // g, k // g)
		dd[nd, nk] += 1
		res.append(dd[nd, nk])
	print(*res)


import collections
import functools
import math
import random
import sys
import bisect
input = sys.stdin.readline

def In():
	return map(int, sys.stdin.readline().split())

def dilkay():
	for _ in range(int(input())):
		d = collections.defaultdict(int)
		n = int(input())
		s = input().rstrip()
		l = [0, 0]
		for i in s:
			if i == 'D':
				l[0] += 1
			else:
				l[1] += 1
			simp = math.gcd(*l)
			tup = (l[0] // simp, l[1] // simp)
			d[tup] += 1
			print(d[tup], end=' ')
dilkay()


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	s = input()
	d = defaultdict(int)
	D = 0
	K = 0
	ans = []
	flag = s[0]
	for i in s:
		if i == flag:
			K += 1
			d[D / K] += 1
			ans.append(d[D / K])
		else:
			D += 1
			d[D / K] += 1
			ans.append(d[D / K])
	print(*ans)


import sys
import math
from bisect import bisect_left
import heapq
from collections import deque
from itertools import product

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
mod = 10 ** 9 + 7
for _ in range(II()):
	n = II()
	s = list(SI())
	ans = [1 for i in range(n)]
	x = 0
	y = 0
	d = {}
	for j in range(n):
		if s[j] == 'D':
			x += 1
		else:
			y += 1
		if x * y == 0:
			ans[j] = j + 1
		else:
			m = math.gcd(x, y)
			if not d.get((x // m, y // m)):
				d[x // m, y // m] = 1
			ans[j] = d[x // m, y // m]
			d[x // m, y // m] += 1
	print(*ans)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	s = input()
	hmm = {}
	dc = 0
	kc = 0
	for i in s:
		if i == 'D':
			dc += 1
		else:
			kc += 1
		if dc == 0 or kc == 0:
			c = 0
		else:
			c = dc / kc
		if c in hmm:
			hmm[c] += 1
		else:
			hmm[c] = 1
		print(hmm[c], end=' ')