Cho Bò Ăn

Farmer John quản lý $N$ con bò ($1\le N\le {10}^5$) đứng tại các vị trí từ $1$ đến $N$. Mỗi con bò thuộc giống Guernsey (G) hoặc Holstein (H). Farmer John cần trồng các ô cỏ để cho bò ăn. Mỗi ô cỏ chứa loại cỏ dành cho Guernsey hoặc Holstein.

Mỗi con bò có thể di chuyển tối đa $K$ vị trí ($0\le K\le N-1$) để đến một ô cỏ phù hợp với giống của nó. Hãy tìm số ô cỏ tối thiểu cần trồng sao cho mọi con bò đều được cho ăn, và đưa ra một cách bố trí hợp lệ.

Dữ liệu vào

• Dòng đầu tiên chứa $T$ ($1\le T\le 10$), số lượng bộ test.
• Với mỗi bộ test:
  • Dòng 1: hai số nguyên $N$ và $K$.
  • Dòng 2: xâu ký tự độ dài $N$ gồm các ký tự 'G' và 'H'.

Dữ liệu ra

Với mỗi bộ test, in ra hai dòng:

• Dòng 1: số ô cỏ tối thiểu cần trồng.
• Dòng 2: xâu ký tự độ dài $N$, mỗi vị trí là '.' (không trồng), 'G' (cỏ Guernsey), hoặc 'H' (cỏ Holstein).

Ràng buộc

• $1\le N\le {10}^5$
• $0\le K\le N-1$
• $1\le T\le 10$

Ví dụ