Busy Beaver đã quyết định tranh cử tổng thống. Thật không may, đối thủ duy nhất của anh ấy là Lazy Lemur quá mạnh, và Busy Beaver không thể thắng bằng các phương pháp thông thường. Vì vậy, anh ấy làm điều mà mọi chính trị gia giỏi đều làm: gian lận bầu cử thông qua phân chia khu vực bầu cử (gerrymandering)!

Đất nước của Busy Beaver bao gồm $N$ thành phố nằm trên một hàng, được đánh số từ $1$ đến $N$. Mỗi thành phố bỏ phiếu cho Lazy Lemur hoặc Busy Beaver làm tổng thống, được biểu diễn bằng $0$ nếu phiếu bầu dành cho Lazy Lemur và $1$ nếu phiếu bầu dành cho Busy Beaver. Tuy nhiên, Busy Beaver có quyền chia $N$ thành phố thành $K$ khối không rỗng gồm các thành phố liên tiếp, trong đó mỗi khối là một khu vực bầu cử. Với mỗi giá trị của $K$ từ $1$ đến $N$, Busy Beaver muốn tối đa hóa số lượng khu vực bầu cử có số phiếu bầu cho anh ấy nhiều hơn hẳn số phiếu bầu cho Lazy Lemur.

Bạn có thể giúp Busy Beaver tìm số lượng khu vực bầu cử tối đa có nhiều phiếu bầu cho anh ấy hơn hẳn đối thủ với $K = 1, \dots, N$ không?

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều trường hợp thử nghiệm. Dòng đầu tiên chứa số lượng trường hợp thử nghiệm $T$ ($1 \le T \le 10^4$). Tiếp theo là mô tả của các trường hợp thử nghiệm.

Dòng đầu tiên của mỗi trường hợp thử nghiệm chứa một số nguyên $N$ ($1 \le N \le 10^5$) mô tả số lượng thành phố.

Dòng thứ hai của mỗi trường hợp thử nghiệm chứa một chuỗi $s$ gồm các ký tự $0$ và $1$ có độ dài $N$, trong đó $s_i$ là $0$ biểu thị Lazy Lemur thắng phiếu bầu của thành phố thứ $i$ và $1$ biểu thị Busy Beaver thắng phiếu bầu của thành phố thứ $i$, với mỗi $i$ từ $1$ đến $N$.

Đảm bảo rằng tổng $N$ trên tất cả các trường hợp thử nghiệm không vượt quá $10^5$.

Dữ liệu ra

Với mỗi trường hợp thử nghiệm, hãy in ra $N$ số nguyên, trong đó số nguyên thứ $K$ đại diện cho số lượng khu vực bầu cử tối đa có nhiều phiếu bầu cho Busy Beaver hơn hẳn sau khi chia các thành phố thành $K$ khối không rỗng gồm các thành phố liên tiếp.

Chấm điểm

• ($10$ điểm) Tổng $N$ trên tất cả các trường hợp thử nghiệm tối đa là $100$.
• ($25$ điểm) Tổng $N$ trên tất cả các trường hợp thử nghiệm tối đa là $3000$.
• ($65$ điểm) Tổng $N$ trên tất cả các trường hợp thử nghiệm tối đa là $10^5$.

Ví dụ

Dữ liệu vào 1

3
3
000
5
01101
8
11011011

Dữ liệu ra 1

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

Ghi chú

Có $3$ trường hợp thử nghiệm.

Trong trường hợp thử nghiệm đầu tiên, Busy Beaver không bao giờ có thể thắng bất kỳ khu vực bầu cử nào vì mọi thành phố đều bỏ phiếu cho Lazy Lemur.

Trong trường hợp thử nghiệm thứ hai, có $5$ thành phố. Với $K = 3$, Busy Beaver có thể thắng $2$ khu vực bầu cử bằng cách chia các thành phố thành các mảng con $[1, 3]$, $[4, 4]$, và $[5, 5]$. Trong $[1, 3]$, $2$ trong số $3$ thành phố bỏ phiếu cho anh ấy. Anh ấy thua ở mảng con $[4, 4]$ vì thành phố duy nhất ở đó không bỏ phiếu cho anh ấy. Anh ấy thắng ở mảng con $[5, 5]$ vì thành phố duy nhất ở đó bỏ phiếu cho anh ấy. Có thể chứng minh rằng Busy Beaver không thể thắng nhiều hơn $2$ khu vực bầu cử.

Lưu ý rằng việc chia thành các mảng con $[1, 2]$, $[3, 4]$, và $[5, 5]$ sẽ chỉ giúp anh ấy thắng $1$ khu vực bầu cử. Cụ thể, anh ấy chỉ thắng một thành phố trong mỗi mảng $[1, 2]$ và $[3, 4]$, và do đó không chiếm đa số tuyệt đối ở bất kỳ khu vực nào trong hai khu vực đó.