문제

Farmer John has $N$ ($1 \le {N} \le {10^5}$) cows, the breed of each being either a Guernsey or a Holstein. They have lined up horizontally with the cows occupying positions labeled from $1\dots N$.

Since all the cows are hungry, FJ decides to plant grassy patches on some of the positions $1\dots N$. Guernseys and Holsteins prefer different types of grass, so if Farmer John decides to plant grass at some location, he must choose to planting either Guernsey-preferred grass or Holstein-preferred grass --- he cannot plant both at the same location. Each patch of grass planted can feed an unlimited number of cows of the appropriate breed.

Each cow is willing to move a maximum of $K$ ($0 \le {K} \le N-1$) positions to reach a patch. Find the minimum number of patches needed to feed all the cows. Also, print a configuration of patches that uses the minimum amount of patches needed to feed the cows. Any configuration that satisfies the above conditions will be considered correct.

입력

Each input contains $T$ test cases, each describing an arrangement of cows. The first line of input contains $T$ ($1 \le T \le 10$). Each of the $T$ test cases follow.

Each test case starts with a line containing $N$ and $K$. The next line will contain a string of length $N$, where each character denotes the breed of the $i$th cow (G meaning Guernsey and H meaning Holstein).

출력

For each of the $T$ test cases, please write two lines of output. For the first line, print the minimum number of patches needed to feed the cows. For the second line, print a string of length $N$ that describes a configuration that feeds all the cows with the minimum number of patches. The $i$th character, describing the $i$th position, should be a '.' if there is no patch, a 'G' if there is a patch that feeds Guernseys, and a 'H' if it feeds Holsteins. Any valid configuration will be accepted.

예제 입력 1

6
5 0
GHHGG
5 1
GHHGG
5 2
GHHGG
5 3
GHHGG
5 4
GHHGG
2 1
GH

예제 출력 1

5
GHHGG
3
.GH.G
2
..GH.
2
...GH
2
...HG
2
HG

점수

Inputs 2 through 4 have $N \le 10$. Inputs 5 through 8 have $N \le 40$. Inputs 9 through 12 have $N \le 10^5$.