Фермер Джон має \(N\) (\(1 \le {N} \le {10^5}\)) корів, кожна з яких має породу або Guernsey (G) або Holstein (H). Вони вишикувалися в ряд зайнявши позиції \(1 \dots N\).

Оскільки всі голодні корови, ФД вирішив викласти пакети з травою в деяких позиціях \(1\dots N\). Корови різних порід їдять різні типи трав. Кожен пакет трави повинен містити траву лише одного типу (для G або H). Він не може розмістити пакети з різною травою в одній позиції. Кожен пакет трави може нагодувати необмежену кількість корів відповідного типу.

Кожна корова готова пройти не більше \(K\) (\(0 \le {K} \le N-1\)) позицій щоб дістатися до пакета із травою. Визначте мінімальну кількість пакетів з травою, необхідну, щоб нагодувати всіх корів. Будь-яка конфігурація, що задовольняє зазначеним вище обмеженням буде розглядатися як коректна.

Формат вхідних даних

Кожен тест складається з \(T\) підтестів, що описують розташування корів. Перший рядок стримає \(T\) (\(1 \le T \le 10\)). Далі слідує \(T\) підтестів.

Кожен підтест починається з рядка, що містить \(N\) і \(K\). Наступний рядок містить рядок довжини \(N\), у якому кожен символ означає породу корови на позиції \(i\) (G або H).

Формат вихідних даних

Для кожного з \(T\) підтестів виведіть два рядки. У першому рядку виведіть мінімальну кількість пакетів із травою, які потрібні. У другому рядку потрібно вивести рядок із символів \(N\), який описує Ваше рішення.

\(i\)-ий символ цього рядка вказує, що потрібно розмістити в позиції \(i\):

'.' - нічого

'G' - пакет із травою типу G

'H' - пакет із травою типу H

Будь-яку коректну конфігурацію буде прийнято.

Приклад вхідних даних

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

Зауважимо, що для деяких тестів може бути кілька правильних конфігурацій. Наприклад для 4-го підтесту інша правильна відповідь така:

.GH..

Це відповідає розміщенню пакета з травою типу G на 2-ій позиції та пакету з травою типу H на позиції 3. Це гарантує що кожної корови її тип їжі перебуває не далі, ніж у 3 позиціях від неї.

• У тестах 2 - 4 \(N \le 10\).
• У тестах 5 - 8 \(N \le 40\).
• У тестах 9 - 12 \(N\le 10^5\).