CF1196D1.RGB Substring (easy version)

The only difference between easy and hard versions is the size of the input.

You are given a string $s$ consisting of $n$ characters, each character is 'R', 'G' or 'B'.

You are also given an integer $k$. Your task is to change the minimum number of characters in the initial string $s$ so that after the changes there will be a string of length $k$ that is a substring of $s$, and is also a substring of the infinite string "RGBRGBRGB ...".

A string $a$ is a substring of string $b$ if there exists a positive integer $i$ such that $a_1 = b_i$, $a_2 = b_{i + 1}$, $a_3 = b_{i + 2}$, ..., $a_{|a|} = b_{i + |a| - 1}$. For example, strings "GBRG", "B", "BR" are substrings of the infinite string "RGBRGBRGB ..." while "GR", "RGR" and "GGG" are not.

You have to answer $q$ independent queries.

简单版本与困难版本的唯一区别在于输入规模。

给你一个由 $n$ 个字符组成的字符串 $s$，其中每个字符为 'R'、'G' 或 'B'。

同时给你一个整数 $k$。你的任务是：在初始字符串 $s$ 中修改最少数量的字符，使得修改后，$s$ 中存在一个长度为 $k$ 的子串，该子串同时也是无限字符串 "RGBRGBRGB ..." 的子串。

若存在某个正整数 $i$，使得 $a_1 = b_i$，$a_2 = b_{i + 1}$，$a_3 = b_{i + 2}$，…，$a_{|a|} = b_{i + |a| - 1}$，则称字符串 $a$ 是字符串 $b$ 的子串。例如，"GBRG"、"B"、"BR" 都是无限字符串 "RGBRGBRGB ..." 的子串，而 "GR"、"RGR" 和 "GGG" 则不是。

你需要回答 $q$ 个相互独立的查询。

The first line of the input contains one integer $q$ ($1 \le q \le 2000$) — the number of queries. Then $q$ queries follow.

The first line of the query contains two integers $n$ and $k$ ($1 \le k \le n \le 2000$) — the length of the string $s$ and the length of the substring.

The second line of the query contains a string $s$ consisting of $n$ characters 'R', 'G' and 'B'.

It is guaranteed that the sum of $n$ over all queries does not exceed $2000$ ($\sum n \le 2000$).

输入的第一行包含一个整数 $q$（$1 \le q \le 2000$），表示查询次数。随后是 $q$ 组查询。

每组查询的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2000$），分别表示字符串 $s$ 的长度以及子串的长度。

每组查询的第二行包含一个由 $n$ 个字符组成的字符串 $s$，其中每个字符为 'R'、'G' 或 'B'。

保证所有查询的 $n$ 值之和不超过 $2000$（即 $\sum n \le 2000$）。

For each query print one integer — the minimum number of characters you need to change in the initial string $s$ so that after changing there will be a substring of length $k$ in $s$ that is also a substring of the infinite string "RGBRGBRGB ...".

对于每个查询，输出一个整数——即需要修改初始字符串 $s$ 中的最少字符数，使得修改后字符串 $s$ 中存在一个长度为 $k$ 的子串，该子串同时也是无限字符串 “RGBRGBRGB...” 的子串。

In the first example, you can change the first character to 'R' and obtain the substring "RG", or change the second character to 'R' and obtain "BR", or change the third, fourth or fifth character to 'B' and obtain "GB".

In the second example, the substring is "BRG".

在第一个例子中，你可以将第一个字符改为 'R'，从而得到子串 "RG"；或将第二个字符改为 'R'，从而得到 "BR"；或者将第三个、第四个或第五个字符改为 'B'，从而得到 "GB"。

在第二个例子中，子串为 "BRG"。