Farmer John 有 N（1≤N≤10^5）头奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。她们沿水平方向排成一行，奶牛们占据的位置编号为 1…N。由于奶牛们都饿了，FJ 决定在 1…N中的某些位置上种植草地。更赛牛和荷斯坦牛喜欢不同类型的草，所以如果 Farmer John 决定在某个位置种草，他必须选择种植更赛牛喜欢的草或荷斯坦牛喜欢的草——他不能在同一个位置同时种两种草。种植的每一片草地都可以喂饱数量不限的相应品种的奶牛。

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

每个测试用例包含 T个子测试用例，为一种奶牛的排列。输入的第一行包含 T（1≤T≤10）。以下是 T个子测试用例。 每个子测试用例的第一行包含 N和 K。第二行包含一个长度为 N 的字符串，其中第 i个字符表示第 i头奶牛的品种（G 表示更赛牛，H 表示荷斯坦牛）。

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

测试点 2-4 满足 N≤10。
测试点 5-8 满足 N≤40。
测试点 9-12 满足 N≤10^5。

USACO 2022 DEC