Busy Beaver는 대통령 선거에 출마하기로 했습니다. 불행히도 유일한 경쟁자인 Lazy Lemur가 너무 강력하여, Busy Beaver는 정상적인 방법으로는 승리할 수 없습니다. 따라서 그는 모든 유능한 정치인이 그렇듯, 게리맨더링을 통해 선거를 조작하기로 했습니다!

Busy Beaver의 나라는 일렬로 나열된 $1$부터 $N$까지 번호가 매겨진 $N$개의 도시로 구성되어 있습니다. 각 도시는 Lazy Lemur에게 투표하면 $0$, Busy Beaver에게 투표하면 $1$로 표시됩니다. Busy Beaver는 $N$개의 도시를 $K$개의 비어 있지 않은 연속된 도시 블록(선거구)으로 나눌 수 있습니다. Busy Beaver는 $1$부터 $N$까지의 모든 $K$에 대하여, 자신이 Lazy Lemur보다 엄격하게 더 많은 표를 얻은 선거구의 수를 최대화하고자 합니다.

$K = 1, \dots, N$ 각각에 대해 Busy Beaver가 얻을 수 있는 최대 선거구 수를 구하도록 도와주세요.

입력

각 테스트 케이스는 여러 개의 테스트 케이스를 포함합니다. 첫 번째 줄에는 테스트 케이스의 수 $T$ ($1 \le T \le 10^4$)가 주어집니다. 각 테스트 케이스에 대한 설명은 다음과 같습니다.

각 테스트 케이스의 첫 번째 줄에는 도시의 수를 나타내는 정수 $N$ ($1 \le N \le 10^5$)이 주어집니다.

각 테스트 케이스의 두 번째 줄에는 $0$과 $1$로 이루어진 길이 $N$의 문자열 $s$가 주어집니다. 여기서 $s_i$가 $0$이면 $i$번째 도시에서 Lazy Lemur가 승리했음을 의미하고, $1$이면 $i$번째 도시에서 Busy Beaver가 승리했음을 의미합니다.

모든 테스트 케이스에 대한 $N$의 합은 $10^5$를 넘지 않음이 보장됩니다.

출력

각 테스트 케이스마다 $N$개의 정수를 출력합니다. 여기서 $K$번째 정수는 도시를 $K$개의 비어 있지 않은 연속된 블록으로 나누었을 때 Busy Beaver가 엄격하게 더 많은 표를 얻은 선거구의 최대 개수를 나타냅니다.

서브태스크

• ($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$개의 테스트 케이스가 있습니다.

첫 번째 테스트 케이스에서, 모든 도시가 Lazy Lemur에게 투표하므로 Busy Beaver는 어떤 선거구에서도 승리할 수 없습니다.

두 번째 테스트 케이스에는 $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]$ 각각에서 그는 단 하나의 도시에서만 승리하므로, 어느 선거구에서도 엄격한 과반수를 차지하지 못합니다.