Đây là phiên bản dễ của bài toán. Khác biệt duy nhất là trong phiên bản này, ~k=1~.

Bạn được cho một xâu nhị phân ~s~ độ dài ~n~. Một đoạn con ~s_l s_{l+1}\dots s_r\ (1\le l\le r\le n)~ được gọi là "đẹp" nếu số ký tự 0 và số ký tự 1 xuất hiện trong đoạn con đó bằng nhau.

Độ đẹp của một xâu nhị phân bằng số đoạn con "đẹp" xuất hiện trong xâu đó.

Bạn được phép thực hiện thao tác sau tối đa ~k~ lần:

• Đổi chỗ hai ký tự kề nhau (~s_i~ và ~s_{i + 1}~).

Nhiệm vụ của bạn là xác định độ đẹp tối đa của xâu có thể đạt được sau khi thực hiện thao tác.

Input

Mỗi bộ test bao gồm nhiều trường hợp thử nghiệm. Dòng đầu tiên gồm số nguyên dương ~t~ là số trường hợp thử nghiệm ~(1\le t\le 10^4)~. Định dạng với mỗi trường hợp thử nghiệm được mô tả như sau:

Dòng đầu tiên trong mỗi trường hợp thử nghiệm gồm hai số nguyên dương ~n~ và ~k\ (1\le n\le 2\times 10^5,k=1)~ - độ dài xâu nhị phân ~s~ và số thao tác tối đa.

Dòng thứ hai trong mỗi trường hợp thử nghiệm gồm một xâu nhị phân ~s~ độ dài ~n~. Dữ liệu đảm bảo ~s~ chỉ bao gồm các ký tự 0 và 1.

Dữ liệu đảm bảo tổng ~n~ trong tất cả trường hợp thử nghiệm không vượt quá ~2\times 10^5~.

Output

Với mỗi trường hợp thử nghiệm, in ra một số nguyên không âm trên một dòng tương ứng với độ đẹp tối đa của xâu ~s~ có thể đạt được.

Sample Input

2
4 1
0110
4 1
0101

Sample Output

4
4

Trong test 1: Chọn ~i=1~ để hoán đổi ~s_1~ và ~s_2~, xâu trở thành 1010. Lúc này số lượng đoạn con đẹp là 4: ~10~, ~01~, ~10~, và ~1010~. Đây là kết quả tối ưu.