暂无测试数据。

Farmer John 有 $N$（$1 \le {N} \le {10^5}$）头奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。她们沿水平方向排成一行，奶牛们占据的位置编号为 $1\dots N$。

由于奶牛们都饿了，FJ 决定在 $1\dots N$ 中的某些位置上种植草地。更赛牛和荷斯坦牛喜欢不同类型的草，所以如果 Farmer John 决定在某个位置种草，他必须选择种植更赛牛喜欢的草或荷斯坦牛喜欢的草——他不能在同一个位置同时种两种草。种植的每一片草地都可以喂饱数量不限的相应品种的奶牛。

每头奶牛愿意移动至多 $K$（$0 \le {K} \le N-1$）个位置以前往一个草地。求出喂饱所有奶牛所需种植的最小草地数量。此外，输出一种使用最小草地数量喂饱所有奶牛的种植方案。任何满足上述条件的方案均视为正确。

输入格式

每个测试用例包含 $T$ 个子测试用例，为一种奶牛的排列。输入的第一行包含 $T$（$1 \le T \le 10$）。以下是 $T$ 个子测试用例。

每个子测试用例的第一行包含 $N$ 和 $K$。第二行包含一个长度为 $N$ 的字符串，其中第 $i$ 个字符表示第 $i$ 头奶牛的品种（G 表示更赛牛，H 表示荷斯坦牛）。

输出格式

对于 $T$ 个子测试用例中的每一个，输出两行。第一行输出喂饱所有奶牛所需的最小草地数量。第二行输出一个长度为 $N$ 的字符串，表示一种使用最小草地数量喂饱所有奶牛的种植方案。第 $i$ 个字符表示第 $i$ 个位置，若不种草则为 ‘.’，若种植喂饱更赛牛的草则为 ‘G’，若种植喂饱荷斯坦牛的草则为 ‘H’。任何合法的方案均可通过。

测试点性质

• 测试点 2-4 满足 $N \le 10$。
• 测试点 5-8 满足 $N \le 40$。
• 测试点 9-12 满足 $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