Bán đá

Một cửa hàng kẹo có một thanh kẹo dài \(N\) cm, được ghép từ \(N\) đoạn dài \(1\) cm. Mỗi đoạn là ngọt (ký hiệu 1) hoặc chua (ký hiệu 0). Người bán có thể bẻ thanh kẹo tại các mối nối giữa hai đoạn liên tiếp để chia nó thành nhiều mẩu liên tiếp (có thể không bẻ chỗ nào, cũng có thể bẻ tại mọi mối nối).

Khách hàng nhỏ tuổi chỉ chịu mua một mẩu nếu trong mẩu đó số đoạn ngọt nhiều hơn hẳn số đoạn chua. Những mẩu không được mua sẽ bị bỏ lại.

Hãy cho biết tổng chiều dài lớn nhất của các mẩu bán được, nếu người bán bẻ thanh kẹo một cách tối ưu.

Input

• Dòng đầu tiên chứa số nguyên \(t\) là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng: dòng thứ nhất chứa số nguyên \(N\); dòng thứ hai chứa xâu gồm \(N\) ký tự 0 hoặc 1 mô tả thanh kẹo từ trái sang phải.

Output

Với mỗi bộ dữ liệu in ra một số nguyên là tổng chiều dài lớn nhất bán được.

Constraints

• \(1 \le t \le 100\)
• \(1 \le N \le 200\)

Sample Input

3
8
11010100
5
00100
11
01110010011

Sample Output

7
1
11

Explanation

Ở bộ thứ nhất, cả thanh có \(4\) đoạn ngọt và \(4\) đoạn chua nên không bán nguyên được; bẻ bỏ đoạn cuối cùng thì mẩu 1101010 (4 ngọt, 3 chua) bán được, dài \(7\). Ở bộ thứ hai chỉ bán được mẩu 1 (dài \(1\)). Ở bộ thứ ba, cả thanh có \(7\) đoạn ngọt và \(4\) đoạn chua nên bán nguyên thanh, được \(11\).