Chứng chỉ giả

Bối cảnh

FullHouse Dev đang xem xét bảng chấm công của một học viên. Bảng chấm công được biểu diễn bằng một chuỗi nhị phân S có độ dài N, trong đó Si = 1 nếu học viên đi học vào ngày thứ i, và Si = 0 nếu học viên vắng mặt.

Yêu cầu

Học viên muốn cải thiện tỷ lệ đi học của mình. Họ có thể thực hiện thao tác sau tối đa một lần:

Chọn bất kỳ chuỗi con nào của S mà học viên vắng mặt mỗi ngày. Sau đó, họ có thể nộp giấy chứng nhận y tế cho khoảng thời gian này và sẽ được đánh dấu là có mặt cho toàn bộ thời gian đó.

Lưu ý rằng chuỗi con là một phân đoạn liên tục của một chuỗi. Ví dụ, "acab" là một chuỗi con của "abacaba", nhưng "aa" hoặc "d" không phải là chuỗi con của chuỗi này.

Bạn cần tìm số ngày tối đa mà học viên sẽ được đánh dấu là có mặt sau khi thực hiện thao tác này tối đa một lần.

Input

• Dòng đầu tiên chứa một số nguyên T - số lượng bộ test.
• Mỗi bộ test gồm hai dòng:
  • Dòng đầu tiên chứa một số nguyên N - độ dài của chuỗi.
  • Dòng thứ hai chứa một chuỗi nhị phân S.

Output

• Với mỗi bộ test, in ra trên một dòng mới số ngày tối đa mà học viên sẽ được đánh dấu là có mặt sau khi thực hiện tối đa một thao tác.

Ràng buộc

• 1 ≤ T ≤ 10^4
• 1 ≤ N ≤ 2⋅10^5
• S là một chuỗi nhị phân
• Tổng của N trên tất cả các bộ test không vượt quá 2⋅10^5.

Ví dụ 1

Input

4
3
111
3
000
6
010010
6
001001

Output

3
3
4
4

Giải thích ví dụ

• Test 1: Học viên có mặt tất cả các ngày nên không cần thực hiện thao tác nào. Số ngày tối đa được đánh dấu có mặt là 3.
• Test 2: Học viên vắng mặt tất cả các ngày nên có thể chọn chuỗi con S[1,3] và chuyển tất cả ngày vắng mặt thành có mặt. Số ngày tối đa được đánh dấu có mặt là 3.
• Test 3: Học viên có thể chọn từ S[1,1], S[3,4] hoặc S[6,6]. Tối ưu nhất là chọn S[3,4] và chuỗi kết quả sẽ là 011110. Số ngày tối đa được đánh dấu có mặt là 4.
• Test 4: Tương tự như test 3, số ngày tối đa được đánh dấu có mặt là 4.

Thông tin học tập

• Buổi: B20
• Concepts: std::string, getline, index, find, substr, basic transformations
• Giới hạn kiến thức: B01-B20
• Time limit: 2 seconds
• Memory limit: 64 MB
• Point: 15