Chia gỗ theo tỉ lệ D:K

Cho một tấm gỗ được biểu diễn bằng một xâu $s$ gồm $n$ ký tự, mỗi ký tự là 'D' hoặc 'K'.

Ta muốn thực hiện một số nhát cắt (có thể là $0$) để chia xâu thành một số đoạn liên tiếp, mỗi đoạn có độ dài ít nhất là $1$. Ta muốn chia sao cho tỉ lệ giữa số lần xuất hiện của 'D' và số lần xuất hiện của 'K' trong mọi đoạn đều bằng nhau. Hãy tìm số đoạn nhiều nhất có thể chia được.

Với một xâu, ta định nghĩa tỉ lệ của nó là $a:b$ nếu 'D' xuất hiện $a$ lần và 'K' xuất hiện $b$ lần. Lưu ý $a$ hoặc $b$ có thể bằng $0$, nhưng không thể cùng bằng $0$. Hai tỉ lệ $a:b$ và $c:d$ được coi là bằng nhau khi và chỉ khi $a·d=b·c$.

Ví dụ, xâu 'DDD' có tỉ lệ $3:0$, xâu 'DKD' có tỉ lệ $2:1$, xâu 'DKK' có tỉ lệ $1:2$, và 'KKKKDD' có tỉ lệ $2:4$. Hai xâu cuối có tỉ lệ bằng nhau, nhưng khác với tỉ lệ của hai xâu đầu.

Ta cần trả lời câu hỏi cho mọi tiền tố của xâu đã cho: với mỗi $i$, tìm số đoạn nhiều nhất khi chia tiền tố $s_1{s}_2\dots s_i$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ test.
• Mỗi bộ test gồm hai dòng: dòng đầu chứa số nguyên $n$ là độ dài tấm gỗ, dòng thứ hai chứa xâu $s$ độ dài $n$ gồm các ký tự 'D' và 'K'.

Dữ liệu ra

Với mỗi bộ test, in ra $n$ số nguyên cách nhau bởi dấu cách. Số thứ $i$ là đáp án cho tiền tố $s_1{s}_2\dots s_i$.

Ràng buộc

• $1\le t\le 1000$
• $1\le n\le 5·{10}^5$
• Tổng $n$ trên tất cả các bộ test không vượt quá $5·{10}^5$.

Ví dụ