Nông dân John có \(N\) (\(1 \le N \le 10^5\)) con bò, mỗi con thuộc một trong hai giống: Guernsey hoặc Holstein. Chúng được xếp hàng theo vị trí từ \(1, 2, \dots, N\).

Vì tất cả các con bò đều đói, Nông dân John quyết định trồng các bãi cỏ tại một số vị trí từ \(1, 2, \dots, N\). Bò Guernsey và bò Holstein thích các loại cỏ khác nhau, do đó nếu bác John quyết định trồng cỏ tại một vị trí, bác phải chọn trồng cỏ dành riêng cho bò Guernsey hoặc bò Holstein --- bác không thể trồng cả hai loại cỏ tại cùng một vị trí. Mỗi bãi cỏ có thể nuôi sống một số lượng không giới hạn bò của giống phù hợp.

Mỗi con bò chỉ sẵn sàng di chuyển tối đa \(K\) (\(0 \le K \le N-1\)) vị trí để đến một bãi cỏ. Hãy tìm số lượng bãi cỏ tối thiểu cần trồng để nuôi sống tất cả các con bò. Đồng thời, in ra một phương án của các bãi cỏ sao cho sử dụng số lượng bãi cỏ tối thiểu đó để nuôi sống tất cả các con bò. Bất kỳ phương án nào thỏa mãn điều kiện trên đều được chấp nhận.

Input

Mỗi input gồm \(T\) bộ test, mỗi bộ mô tả một dãy bò. Dòng đầu tiên của input chứa \(T\) (\(1 \le T \le 10\)) là số lượng test. Mỗi bộ test tiếp theo bao gồm:

• Dòng đầu tiên là \(2\) số nguyên \(N\) và \(K\).
• Dòng tiếp theo chứa một chuỗi ký tự độ dài \(N\), trong đó mỗi ký tự đại diện cho giống của con bò thứ \(i\) (\(G\) nghĩa là Guernsey, \(H\) nghĩa là Holstein).

Output

Với mỗi bộ test trong \(T\) bộ test, hãy in ra hai dòng output:

• Dòng đầu tiên in ra số lượng bãi cỏ tối thiểu cần trồng để nuôi sống tất cả các con bò.
• Dòng thứ hai in ra một chuỗi độ dài \(N\) mô tả phương án trồng các bãi cỏ thỏa mãn điều kiện nuôi sống tất cả các con bò với số lượng bãi cỏ tối thiểu. Ký tự thứ \(i\) trong chuỗi là:
• . nếu tại vị trí đó không trồng bãi cỏ nào,
• G nếu trồng bãi cỏ cho bò Guernsey,
• H nếu trồng bãi cỏ cho bò Holstein.

Bất kỳ phương án hợp lệ nào đều được chấp nhận.

Scoring

• Subtask \(1\): \(N \le 10\).
• Subtask \(2\): \(N \le 40\).
• Subtask \(3\)L \(N \le 10^5\).

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

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

.GH..