Kiến trúc thường là kết quả của sự va chạm giữa hai bộ óc xuất chúng nhưng có tư tưởng đối lập. Kotori và Umi, hai kiến trúc sư trưởng của một đại lộ đi bộ mới trong thành phố, đang rơi vào thế bế tắc về định hướng thẩm mỹ của mặt đường lát đá. Đại lộ được mô hình hóa thành một dãy gồm $n$ ô nằm trên một hàng duy nhất.

Một số ô đã được lát đá: một số chứa đá cẩm thạch trắng đặc trưng của Kotori, trong khi một số khác chứa đá hoa cương đen ưa thích của Umi. Nhiều ô vẫn còn trống (được đánh dấu là "?"). Bây giờ Kotori và Umi phải lần lượt lấp đầy các ô còn lại từng ô một.

Để đảm bảo sự công bằng tuyệt đối trong quá trình hợp tác và ngăn không cho bất kỳ triết lý đơn lẻ nào chiếm ưu thế mà không có sự cạnh tranh, họ đã thống nhất một quy tắc thiết kế chính thức:

• Kotori và Umi lần lượt đặt một viên đá vào một ô trống, với Kotori là người đi trước.
• Kotori luôn đặt một viên đá cẩm thạch trắng, vì cô tin rằng vẻ đẹp của đại lộ được đo bằng đoạn liên tiếp dài nhất gồm các viên đá cẩm thạch trắng. Tự nhiên cô tìm cách cực đại hóa độ dài này.
• Umi, người tìm cách tạo ra sự tương phản cấu trúc và nhịp điệu, tin rằng những đoạn màu trắng dài không ngắt quãng thật đơn điệu. Cô luôn đặt một viên đá hoa cương đen, nhằm mục đích cực tiểu hóa chính độ dài cực đại đó.

Một khi viên đá đã được đặt xuống, nó không thể bị di chuyển hoặc thay thế. Quá trình tiếp tục cho đến khi tất cả các ô trống đều được lấp đầy.

Cho trạng thái ban đầu của đại lộ, nhiệm vụ của bạn là xác định "Điểm Thẩm Mỹ" cuối cùng — độ dài của đoạn liên tiếp dài nhất gồm các viên đá cẩm thạch trắng — giả sử cả hai kiến trúc sư đều chơi tối ưu để đạt được mục tiêu thẩm mỹ của riêng mình.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 10^4$) cho biết số lượng bộ dữ liệu. Đối với mỗi bộ dữ liệu:

Dòng đầu tiên và duy nhất chứa một xâu $s_1 s_2 \dots s_n$ có độ dài $n$ ($1 \le n \le 10^5$), trong đó:

• 0 biểu thị một ô đã chứa đá cẩm thạch trắng của Kotori;
• 1 biểu thị một ô đã chứa đá hoa cương đen của Umi;
• ? biểu thị một ô hiện đang trống.

Dữ liệu đảm bảo tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $10^6$.

Kết quả

Đối với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên cho biết điểm số cuối cùng của trò chơi.

Ví dụ

Dữ liệu vào 1

6
??
000
111
0??0??0
0?0?0?0
00?00?100?0

Kết quả 1

1
3
0
3
5
5