Thay thế một phần

Cho số nguyên $k$ và một xâu $s$ độ dài $n$ chỉ gồm hai ký tự '.' và ''. Bạn cần thay một số ký tự '' thành 'x' sao cho thoả mãn tất cả các điều kiện sau:

• Ký tự '*' đầu tiên trong $s$ phải được thay thành 'x'.
• Ký tự '*' cuối cùng trong $s$ phải được thay thành 'x'.
• Khoảng cách giữa hai ký tự 'x' liền kề không được vượt quá $k$. Cụ thể, nếu bạn thay hai vị trí $i$ và $j$ (với $i<j$) thành 'x' và trong đoạn $[i+1,j-1]$ không còn ký tự 'x' nào khác, thì $j-i$ phải không vượt quá $k$.

Hãy tìm số lượng ít nhất các ký tự '*' cần thay thành 'x' để thoả mãn các điều kiện trên.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$: số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng:
  • Dòng thứ nhất chứa hai số nguyên $n$ và $k$.
  • Dòng thứ hai chứa xâu $s$ độ dài $n$ chỉ gồm các ký tự '.' và '*'.

Dữ liệu bảo đảm trong $s$ có ít nhất một ký tự '', và khoảng cách giữa hai ký tự '' liền kề bất kỳ không vượt quá $k$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số lượng ít nhất các ký tự '*' cần thay thành 'x'.

Ràng buộc

• $1\le t\le 500$
• $1\le k\le n\le 50$

Ví dụ