Busy Beaver 決定參選總統。不幸的是，他唯一的對手 Lazy Lemur 太過強大，Busy Beaver 無法透過正常手段獲勝。因此，他決定採取所有優秀政治家都會做的事：透過選區劃分來操縱選舉！

透過選區劃分來操縱選舉！

Busy Beaver 的國家由 $N$ 個城市組成，排成一列，編號為 $1$ 到 $N$。每個城市投票給 Lazy Lemur 或 Busy Beaver，以 $0$ 代表投給 Lazy Lemur，以 $1$ 代表投給 Busy Beaver。然而，Busy Beaver 可以將這 $N$ 個城市劃分為 $K$ 個非空的連續城市區塊，每個區塊即為一個選區。對於 $1$ 到 $N$ 的每一個 $K$ 值，Busy Beaver 希望最大化那些投給他的票數嚴格多於投給 Lazy Lemur 的選區數量。

你能幫助 Busy Beaver 找出對於 $K = 1, \dots, N$ 時，擁有嚴格多數票的選區之最大數量嗎？

輸入格式

每個測試包含多個測試案例。第一行包含測試案例數量 $T$ ($1 \le T \le 10^4$)。接著是各測試案例的描述。

每個測試案例的第一行包含一個整數 $N$ ($1 \le N \le 10^5$)，描述城市的數量。

每個測試案例的第二行包含一個長度為 $N$ 的字串 $s$，由 $0$ 和 $1$ 組成。對於每個 $i$ 從 $1$ 到 $N$，$s_i$ 為 $0$ 表示 Lazy Lemur 贏得第 $i$ 個城市的投票，$1$ 表示 Busy Beaver 贏得第 $i$ 個城市的投票。

保證所有測試案例的 $N$ 之總和不超過 $10^5$。

輸出格式

對於每個測試案例，輸出 $N$ 個整數，其中第 $K$ 個整數代表將城市劃分為 $K$ 個非空連續區塊後，投給 Busy Beaver 的票數嚴格多於投給 Lazy Lemur 的選區之最大數量。

子任務

• ($10$ 分) 所有測試案例的 $N$ 之總和至多為 $100$。

• ($25$ 分) 所有測試案例的 $N$ 之總和至多為 $3000$。

• ($65$ 分) 所有測試案例的 $N$ 之總和至多為 $10^5$。

範例

輸入格式 1

3
3
000
5
01101
8
11011011

輸出格式 1

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

說明

共有 $3$ 個測試案例。

在第一個測試案例中，Busy Beaver 無法贏得任何選區，因為每個城市都投給了 Lazy Lemur。

在第二個測試案例中，共有 $5$ 個城市。對於 $K = 3$，Busy Beaver 可以透過將城市劃分為子陣列 $[1, 3]$、$[4, 4]$ 和 $[5, 5]$ 來贏得 $2$ 個選區。在 $[1, 3]$ 中，$3$ 個城市中有 $2$ 個投給他。他在子陣列 $[4, 4]$ 中落敗，因為該處唯一的城市沒有投給他。他在子陣列 $[5, 5]$ 中獲勝，因為該處唯一的城市投給了他。可以證明 Busy Beaver 無法贏得超過 $2$ 個選區。

請注意，若劃分為子陣列 $[1, 2]$、$[3, 4]$ 和 $[5, 5]$，他只能贏得 $1$ 個選區。特別是，他在 $[1, 2]$ 和 $[3, 4]$ 中各只贏得一個城市，因此在任何一個選區中都沒有取得嚴格多數。