Giãn Cách Chỗ Ngồi

Một nhà hàng có $n$ bàn xếp thành một hàng thẳng, đánh số từ $1$ đến $n$ theo thứ tự từ trái sang phải. Một số bàn đã có người ngồi.

Nội quy nhà hàng yêu cầu hai người bất kỳ không được ngồi cách nhau một khoảng nhỏ hơn hoặc bằng $k$. Nói cách khác, nếu một người ngồi ở bàn $i$ thì mọi bàn có số hiệu từ $i-k$ đến $i+k$ (trừ chính bàn $i$) đều phải trống. Tương đương: hiệu số hiệu của hai bàn có người bất kỳ phải lớn hơn $k$ (lớn hơn thực sự).

Trạng thái hiện tại của nhà hàng được cho bằng một xâu nhị phân $s$ độ dài $n$, trong đó ký tự "1" nghĩa là bàn đó đã có người và "0" nghĩa là bàn trống. Xâu $s$ được đảm bảo đã thỏa mãn nội quy.

Hãy tìm số lượng bàn trống nhiều nhất có thể có thêm người ngồi vào mà vẫn không vi phạm nội quy. Nói cách khác, có thể đổi nhiều nhất bao nhiêu ký tự "0" thành "1" sao cho điều kiện vẫn được giữ nguyên?

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$: số lượng bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa hai số nguyên $n$ và $k$.
  • Dòng thứ hai chứa xâu nhị phân $s$ độ dài $n$ gồm các ký tự "0" và "1", thỏa mãn nội quy (hiệu số hiệu của hai bàn có người bất kỳ đều lớn hơn $k$).

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên: số bàn nhiều nhất có thể thêm người ngồi vào. Nếu không thể thêm bàn nào, in ra $0$.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le k\le n\le 2·{10}^5$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^5$.

Ví dụ