Little Cyan Fish có một hàng gồm $n$ quả bóng. Mỗi quả bóng là màu lục lam (cyan) hoặc màu trắng. Hàng này được mô tả bởi một xâu $s$ có độ dài $n$, trong đó $C$ biểu thị quả bóng màu lục lam và $W$ biểu thị quả bóng màu trắng.

Trong một thao tác, cậu ấy chọn một quả bóng màu lục lam trong hàng hiện tại. Giả sử quả bóng này nằm ở vị trí $i$ trong hàng hiện tại. Khi đó, tất cả các quả bóng có vị trí cách $i$ một khoảng không quá $k$ sẽ bị xóa, bao gồm cả quả bóng màu lục lam đã chọn. Sau khi xóa, các phần còn lại ở bên trái và bên phải sẽ được ghép lại với nhau.

Ví dụ, khi $k = 1$, một thao tác có thể là:

trong đó quả bóng có viền dày được chọn và các quả bóng bên trong khung đỏ bị xóa.

Hãy tìm số lượng thao tác tối thiểu cần thiết để xóa toàn bộ hàng. Nếu không thể thực hiện được, hãy báo cáo điều đó.

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 duy nhất $T$ ($1 \le T$), biểu thị số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($1 \le k \le n \le 10^6$). Dòng thứ hai chứa một xâu $s$ có độ dài $n$, chỉ bao gồm các ký tự $C$ và $W$.

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

Dữ liệu ra

Đối với mỗi bộ dữ liệu, nếu không thể xóa toàn bộ hàng, hãy in ra một dòng duy nhất chứa số nguyên $-1$. Nếu không, hãy in ra một dòng duy nhất chứa một số nguyên, biểu thị số lượng thao tác tối thiểu cần thiết để xóa toàn bộ hàng.

Ví dụ

Dữ liệu vào 1

3
1 1
C
5 2
WWCWW
4 1
WWWW

Dữ liệu ra 1

1
1
-1

Ghi chú

Trong bộ dữ liệu mẫu đầu tiên, Little Cyan Fish chọn quả bóng duy nhất.

Trong bộ dữ liệu mẫu thứ hai, cậu ấy chọn quả bóng màu lục lam ở giữa; vì $k = 2$, toàn bộ hàng bị xóa trong một thao tác.

Trong bộ dữ liệu mẫu thứ ba, không có quả bóng màu lục lam nào, vì vậy không thể thực hiện thao tác nào.