#include <bits/stdc++.h>
#pragma GCC optimize("-O2")
using namespace std;
class UnionFind {
 public:
  vector<int> p, rank;
  UnionFind(int N) {
    rank.assign(N, 1);
    p.assign(N, 0);
    for (int i = 0; i < N; i++) p[i] = i;
  }
  int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
  bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
  void unionSet(int i, int j) {
    if (!isSameSet(i, j)) {
      int x = findSet(i), y = findSet(j);
      if (rank[x] > rank[y])
        p[y] = x, rank[x] += rank[y];
      else {
        p[x] = y;
        rank[y] += rank[x];
      }
    }
  }
};
class RMQ {
 public:
  struct node {
    int mn, mx, l, r;
  };
  vector<int> h;
  vector<node> st;
  bool is_intersection(int l, int r, int ll, int rr) {
    if (r < ll || rr < l) return 0;
    return 1;
  }
  RMQ(vector<int> a) {
    h = a;
    st.resize(4 * h.size());
    build(0, h.size() - 1);
  }
  void build(int l, int r, int k = 0) {
    st[k].l = l, st[k].r = r;
    if (l == r) {
      st[k].mx = st[k].mn = l;
      return;
    }
    build(l, (l + r) / 2, 2 * k + 1);
    build((l + r) / 2 + 1, r, 2 * k + 2);
    if (h[st[2 * k + 1].mn] <= h[st[2 * k + 2].mn])
      st[k].mn = st[2 * k + 1].mn;
    else
      st[k].mn = st[2 * k + 2].mn;
    if (h[st[2 * k + 1].mx] >= h[st[2 * k + 2].mx])
      st[k].mx = st[2 * k + 1].mx;
    else
      st[k].mx = st[2 * k + 2].mx;
  }
  int minquery(int l, int r, int k = 0) {
    if (l > r) return 1000000000;
    int ll = st[k].l, rr = st[k].r, mid = (ll + rr) / 2;
    if (ll >= l && rr <= r) return st[k].mn;
    int ans = l;
    if (!(r < ll || mid < l)) ans = minquery(l, r, 2 * k + 1);
    if (!(r < mid + 1 || rr < l)) {
      if (h[ans] > h[minquery(l, r, 2 * k + 2)])
        ans = minquery(l, r, 2 * k + 2);
    }
    return ans;
  }
  int maxquery(int l, int r, int k = 0) {
    if (l > r) return -1000000000;
    int ll = st[k].l, rr = st[k].r, mid = (ll + rr) / 2;
    if (ll >= l && rr <= r) return st[k].mx;
    int ans = l;
    if (!(r < ll || mid < l)) ans = maxquery(l, r, 2 * k + 1);
    if (!(r < mid + 1 || rr < l)) {
      if (h[ans] < h[maxquery(l, r, 2 * k + 2)])
        ans = maxquery(l, r, 2 * k + 2);
    }
    return ans;
  }
  void update(int id, int val, int k = 0) {
    int l = st[k].l, r = st[k].r, mid = (l + r) / 2;
    if (l == r) {
      h[l] = val;
      return;
    }
    if (id >= l && id <= mid) update(id, val, 2 * k + 1);
    if (mid + 1 <= id && id <= r) update(id, val, 2 * k + 2);
    if (h[st[2 * k + 1].mn] <= h[st[2 * k + 2].mn])
      st[k].mn = st[2 * k + 1].mn;
    else
      st[k].mn = st[2 * k + 2].mn;
    if (h[st[2 * k + 1].mx] >= h[st[2 * k + 2].mx])
      st[k].mx = st[2 * k + 1].mx;
    else
      st[k].mx = st[2 * k + 2].mx;
  }
};
class LAZY {
 public:
  struct node {
    int l, r, lazy = 0;
    long long int lazyval = 0;
    long long int sum = 0;
  };
  vector<node> st;
  vector<int> h;
  LAZY(vector<int> a) {
    h = a;
    st.resize(4 * h.size());
    cst(0, h.size() - 1);
  }
  int intersectiontype1(int l, int r, int ll, int rr) {
    if (r < ll || rr < l) return 0;
    return 1;
  }
  void cst(int l, int r, int k = 0) {
    st[k].l = l, st[k].r = r;
    if (l == r) {
      st[k].sum = h[l];
      return;
    }
    cst(l, (l + r) / 2, 2 * k + 1);
    cst((l + r) / 2 + 1, r, 2 * k + 2);
    st[k].sum = st[2 * k + 1].sum + st[2 * k + 2].sum;
  }
  void shift(int k) {
    st[k].sum = (st[k].r - st[k].l + 1) * st[k].lazyval;
    if (st[k].l != st[k].r) {
      st[2 * k + 1].lazyval = st[k].lazyval;
      st[2 * k + 2].lazyval = st[k].lazyval;
      st[2 * k + 1].lazy = st[2 * k + 1].lazy = 1;
      st[2 * k + 2].lazy = st[2 * k + 2].lazy = 1;
    }
    st[k].lazyval = 0;
    st[k].lazy = 0;
  }
  long long int query(int l, int r, int k = 0) {
    if (st[k].lazy != 0) shift(k);
    int ll = st[k].l, rr = st[k].r, mid = (ll + rr) / 2;
    if (ll >= l && rr <= r) return st[k].sum;
    long long int ans = 0;
    if (intersectiontype1(ll, mid, l, r) == 1) ans = query(l, r, 2 * k + 1);
    if (intersectiontype1(1 + mid, rr, l, r) == 1)
      ans += query(l, r, 2 * k + 2);
    return ans;
  }
  void update(int l, int r, long long int x, int k = 0) {
    if (l > r) return;
    int ll = st[k].l, rr = st[k].r, mid = (ll + rr) / 2;
    if (ll >= l && rr <= r) {
      st[k].lazyval = x;
      st[k].lazy = 1;
      return;
    }
    if (st[k].lazy != 0) shift(k);
    if (st[k].l == st[k].r) return;
    if (intersectiontype1(ll, mid, l, r) == 1) update(l, r, x, 2 * k + 1);
    if (intersectiontype1(mid + 1, rr, l, r) == 1) update(l, r, x, 2 * k + 2);
    if (st[2 * k + 1].lazy != 0) shift(2 * k + 1);
    if (st[2 * k + 2].lazy != 0) shift(2 * k + 2);
    st[k].sum = st[2 * k + 1].sum + st[2 * k + 2].sum;
  }
  int lower_bound(int l, int r, int val) {
    while (l != r) {
      int mid = (l + r) / 2;
      if (query(mid, mid) >= val)
        r = mid;
      else {
        l = mid + 1;
        if (mid + 1 < h.size())
          if (query(mid + 1, mid + 1) > val) {
            l = mid;
            break;
          }
      }
    }
    return l;
  }
};
class span {
 public:
  vector<int> a;
  span(){};
  vector<int> max_left_border_without_equality() {
    int n = a.size();
    vector<int> ta, al(n);
    for (long long int i = 0; i < n; i++) {
      if (ta.size() == 0) {
        ta.push_back(i);
        al[i] = i;
      } else {
        while (a[i] > a[ta[ta.size() - 1]]) {
          ta.pop_back();
          if (ta.size() == 0) break;
        }
        if (ta.size() == 0) {
          ta.push_back(i);
          al[i] = 0;
        } else {
          al[i] = ta[ta.size() - 1] + 1;
          ta.push_back(i);
        }
      }
    }
    return al;
  }
  vector<int> max_left_border_with_equality() {
    int n = a.size();
    vector<int> ta, al(n);
    for (long long int i = 0; i < n; i++) {
      if (ta.size() == 0) {
        ta.push_back(i);
        al[i] = i;
      } else {
        while (a[i] >= a[ta[ta.size() - 1]]) {
          ta.pop_back();
          if (ta.size() == 0) break;
        }
        if (ta.size() == 0) {
          ta.push_back(i);
          al[i] = 0;
        } else {
          al[i] = ta[ta.size() - 1] + 1;
          ta.push_back(i);
        }
      }
    }
    return al;
  }
  vector<int> min_left_border_without_equality() {
    int n = a.size();
    vector<int> ta, al(n);
    for (long long int i = 0; i < n; i++) {
      if (ta.size() == 0) {
        ta.push_back(i);
        al[i] = i;
      } else {
        while (a[i] < a[ta[ta.size() - 1]]) {
          ta.pop_back();
          if (ta.size() == 0) break;
        }
        if (ta.size() == 0) {
          ta.push_back(i);
          al[i] = 0;
        } else {
          al[i] = ta[ta.size() - 1] + 1;
          ta.push_back(i);
        }
      }
    }
    return al;
  }
  vector<int> min_left_border_with_equality() {
    int n = a.size();
    vector<int> ta, al(n);
    for (long long int i = 0; i < n; i++) {
      if (ta.size() == 0) {
        ta.push_back(i);
        al[i] = i;
      } else {
        while (a[i] <= a[ta[ta.size() - 1]]) {
          ta.pop_back();
          if (ta.size() == 0) break;
        }
        if (ta.size() == 0) {
          ta.push_back(i);
          al[i] = 0;
        } else {
          al[i] = ta[ta.size() - 1] + 1;
          ta.push_back(i);
        }
      }
    }
    return al;
  }
  vector<int> max_right_border_without_equality() {
    int n = a.size();
    reverse(a.begin(), a.end());
    vector<int> ans = max_left_border_without_equality();
    reverse(ans.begin(), ans.end());
    for (long long int i = 0; i < n; i++) ans[i] = n - 1 - ans[i];
    reverse(a.begin(), a.end());
    return ans;
  }
  vector<int> max_right_border_with_equality() {
    int n = a.size();
    reverse(a.begin(), a.end());
    vector<int> ans = max_left_border_with_equality();
    reverse(ans.begin(), ans.end());
    for (long long int i = 0; i < n; i++) ans[i] = n - 1 - ans[i];
    reverse(a.begin(), a.end());
    return ans;
  }
  vector<int> min_right_border_without_equality() {
    int n = a.size();
    reverse(a.begin(), a.end());
    vector<int> ans = min_left_border_without_equality();
    reverse(ans.begin(), ans.end());
    for (long long int i = 0; i < n; i++) ans[i] = n - 1 - ans[i];
    reverse(a.begin(), a.end());
    return ans;
  }
  vector<int> min_right_border_with_equality() {
    int n = a.size();
    reverse(a.begin(), a.end());
    vector<int> ans = min_left_border_with_equality();
    reverse(ans.begin(), ans.end());
    for (long long int i = 0; i < n; i++) ans[i] = n - 1 - ans[i];
    reverse(a.begin(), a.end());
    return ans;
  }
};
class merge_sort_tree {
 public:
  long long int cnt(long long int x, vector<int> &arr) {
    long long int n = arr.size();
    vector<int>::iterator low, high;
    low = lower_bound(arr.begin(), arr.end(), x);
    if (low == (arr.end()) || *low != x) return 0;
    high = upper_bound(low, arr.end(), x);
    return high - low;
  }
  long long int get_last_smaller(vector<int> &v, int x) {
    long long int first = 0, last = v.size() - 1;
    while (first <= last) {
      long long int mid = (first + last) / 2;
      if (v[mid] >= x)
        last = mid - 1;
      else
        first = mid + 1;
    }
    return first - 1 < 0 ? -1 : first - 1;
  }
  struct node {
    int l, r;
    vector<int> arr;
  };
  vector<int> a;
  vector<node> st;
  merge_sort_tree(vector<int> b) {
    st.resize(4 * b.size());
    a = b;
    build(0, b.size() - 1);
  }
  void build(int l, int r, int k = 0) {
    st[k].l = l, st[k].r = r;
    for (int i = l; i < r + 1; i++) st[k].arr.push_back(a[i]);
    sort(st[k].arr.begin(), st[k].arr.end());
    if (l == r) return;
    build(l, (l + r) / 2, 2 * k + 1);
    build((l + r) / 2 + 1, r, 2 * k + 2);
  }
  bool intersection(int l, int r, int ll, int rr) {
    if (ll > r || l > rr) return 0;
    return 1;
  }
  long long int count_val_in_range(int l, int r, int t, int k = 0) {
    if (l > r) return 0;
    int ll = st[k].l, rr = st[k].r, mid = (ll + rr) / 2;
    if (ll >= l && rr <= r) return cnt(t, st[k].arr);
    long long int ans = 0;
    if (intersection(l, r, ll, mid) == 1)
      ans += count_val_in_range(l, r, t, 2 * k + 1);
    if (intersection(l, r, mid + 1, rr) == 1)
      ans += count_val_in_range(l, r, t, 2 * k + 2);
    return ans;
  }
  long long int count_vals_less_than_given_val(int l, int r, int t, int k,
                                               vector<node> &st) {
    if (l > r) return 0;
    int ll = st[k].l, rr = st[k].r, mid = (ll + rr) / 2;
    if (ll >= l && rr <= r) return get_last_smaller(st[k].arr, t) + 1;
    long long int ans = 0;
    if (intersection(l, r, ll, mid) == 1)
      ans += count_vals_less_than_given_val(l, r, t, 2 * k + 1, st);
    if (intersection(l, r, mid + 1, rr) == 1)
      ans += count_vals_less_than_given_val(l, r, t, 2 * k + 2, st);
    return ans;
  }
};
void DEBUG_ARR(vector<int> a) {
  for (long long int i = 0; i < a.size(); i++) cout << a[i] << " ";
  cout << "\n";
}
long long int tmod(long long int x, long long int m) { return (x % m + m) % m; }
long long int power(long long int x, long long int y) {
  long long int res = 1;
  while (y > 0) {
    if (y & 1) res = (res * x) % 1000000007;
    y = y >> 1;
    x = (x * x) % 1000000007;
  }
  if (res < 0) res += 1000000007;
  return res;
}
long long int modInverse(long long int a, long long int m) {
  long long int m0 = m;
  long long int y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    long long int q = a / m;
    long long int t = m;
    m = a % m, a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}
vector<int> tree[100001];
long long int contribution[100001], subtree_size[100001];
vector<long long int> wt[100001];
vector<int> parent(100001, 0);
int n;
void set_contribution(int u, int p) {
  subtree_size[u] = 1;
  for (auto x : tree[u]) {
    if (x == p) continue;
    set_contribution(x, u);
    parent[x] = u;
    subtree_size[u] += subtree_size[x];
    contribution[x] = (n - subtree_size[x]) * subtree_size[x];
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int q;
  cin >> q;
  while (q != 0) {
    q--;
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    if (k == 1) {
      cout << 0 << "\n";
      continue;
    }
    if (k == 2) {
      int f1 = false, f2 = false, f3 = false;
      for (long long int i = 0; i < n - 1; i++) {
        if (s[i] == 'R' && s[i + 1] == 'G')
          f1 = true;
        else if (s[i] == 'G' && s[i + 1] == 'B')
          f2 = true;
        else if (s[i] == 'B' && s[i + 1] == 'R')
          f3 = true;
      }
      if (f1 == 1 || f2 == 1 || f3 == 1)
        cout << 0 << "\n";
      else
        cout << 1 << "\n";
      continue;
    }
    int dp[n][3];
    for (long long int i = 0; i < n; i++)
      for (long long int j = 0; j < 3; j++) dp[i][j] = 0;
    for (long long int i = 0; i < k / 3; i++) {
      dp[0][0] +=
          (s[3 * i] != 'R') + (s[3 * i + 1] != 'G') + (s[3 * i + 2] != 'B');
      dp[0][1] +=
          (s[3 * i] != 'G') + (s[3 * i + 1] != 'B') + (s[3 * i + 2] != 'R');
      dp[0][2] +=
          (s[3 * i] != 'B') + (s[3 * i + 1] != 'R') + (s[3 * i + 2] != 'G');
    }
    int p = k / 3;
    if (k % 3 == 1) {
      dp[0][0] += (s[3 * p] != 'R');
      dp[0][1] += (s[3 * p] != 'G');
      dp[0][2] += (s[3 * p] != 'B');
    } else if (k % 3 == 2) {
      dp[0][0] += (s[3 * p] != 'R') + (s[3 * p + 1] != 'G');
      dp[0][1] += (s[3 * p] != 'G') + (s[3 * p + 1] != 'B');
      dp[0][2] += (s[3 * p] != 'B') + (s[3 * p + 1] != 'R');
    }
    for (long long int i = 0; i < k / 3; i++) {
      dp[1][0] +=
          (s[3 * i + 1] != 'R') + (s[3 * i + 2] != 'G') + (s[3 * i + 3] != 'B');
      dp[1][1] +=
          (s[3 * i + 1] != 'G') + (s[3 * i + 2] != 'B') + (s[3 * i + 3] != 'R');
      dp[1][2] +=
          (s[3 * i + 1] != 'B') + (s[3 * i + 2] != 'R') + (s[3 * i + 3] != 'G');
    }
    if (k % 3 == 1) {
      dp[1][0] += (s[3 * p + 1] != 'R');
      dp[1][1] += (s[3 * p + 1] != 'G');
      dp[1][2] += (s[3 * p + 1] != 'B');
    } else if (k % 3 == 2) {
      dp[1][0] += (s[3 * p + 1] != 'R') + (s[3 * p + 2] != 'G');
      dp[1][1] += (s[3 * p + 1] != 'G') + (s[3 * p + 2] != 'B');
      dp[1][2] += (s[3 * p + 1] != 'B') + (s[3 * p + 2] != 'R');
    }
    for (long long int i = 0; i < k / 3; i++) {
      dp[2][0] +=
          (s[3 * i + 2] != 'R') + (s[3 * i + 3] != 'G') + (s[3 * i + 4] != 'B');
      dp[2][1] +=
          (s[3 * i + 2] != 'G') + (s[3 * i + 3] != 'B') + (s[3 * i + 4] != 'R');
      dp[2][2] +=
          (s[3 * i + 2] != 'B') + (s[3 * i + 3] != 'R') + (s[3 * i + 4] != 'G');
    }
    if (k % 3 == 1) {
      dp[2][0] += (s[3 * p + 2] != 'R');
      dp[2][1] += (s[3 * p + 2] != 'G');
      dp[2][2] += (s[3 * p + 2] != 'B');
    } else if (k % 3 == 2) {
      dp[2][0] += (s[3 * p + 2] != 'R') + (s[3 * p + 3] != 'G');
      dp[2][1] += (s[3 * p + 2] != 'G') + (s[3 * p + 3] != 'B');
      dp[2][2] += (s[3 * p + 2] != 'B') + (s[3 * p + 3] != 'R');
    }
    char at[3] = {'R', 'G', 'B'}, mp[3];
    for (long long int i = 0; i < 3; i++) mp[i] = at[(i + k) % 3];
    for (long long int i = 3; i < n - k + 1; i++) {
      dp[i][0] = dp[i - 3][0] + (s[i + k - 3] != mp[0]) +
                 (s[i + k - 2] != mp[1]) + (s[i + k - 1] != mp[2]) -
                 (s[i - 3] != 'R') - (s[i - 2] != 'G') - (s[i - 1] != 'B');
      dp[i][1] = dp[i - 3][1] + (s[i + k - 3] != mp[1]) +
                 (s[i + k - 2] != mp[2]) + (s[i + k - 1] != mp[0]) -
                 (s[i - 3] != 'G') - (s[i - 2] != 'B') - (s[i - 1] != 'R');
      dp[i][2] = dp[i - 3][2] + (s[i + k - 3] != mp[2]) +
                 (s[i + k - 2] != mp[0]) + (s[i + k - 1] != mp[1]) -
                 (s[i - 3] != 'B') - (s[i - 2] != 'R') - (s[i - 1] != 'G');
    }
    int ans = 1000000000;
    for (long long int i = 0; i < n - k + 1; i++) ans = min(ans, dp[i][0]);
    for (long long int i = 0; i < n - k + 1; i++) ans = min(ans, dp[i][1]);
    for (long long int i = 0; i < n - k + 1; i++) ans = min(ans, dp[i][2]);
    cout << ans << "\n";
  }
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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.

Input

The first line of the input contains one integer q (1 ≤ q ≤ 2 ⋅ 10^5) — the number of queries. Then q queries follow.

The first line of the query contains two integers n and k (1 ≤ k ≤ n ≤ 2 ⋅ 10^5) — 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 2 ⋅ 10^5 (∑ n ≤ 2 ⋅ 10^5).

Output

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 ...".

Example

Input


3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR


Output


1
0
3

Note

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".

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("-O2")
using namespace std;
class UnionFind {
 public:
  vector<int> p, rank;
  UnionFind(int N) {
    rank.assign(N, 1);
    p.assign(N, 0);
    for (int i = 0; i < N; i++) p[i] = i;
  }
  int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
  bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
  void unionSet(int i, int j) {
    if (!isSameSet(i, j)) {
      int x = findSet(i), y = findSet(j);
      if (rank[x] > rank[y])
        p[y] = x, rank[x] += rank[y];
      else {
        p[x] = y;
        rank[y] += rank[x];
      }
    }
  }
};
class RMQ {
 public:
  struct node {
    int mn, mx, l, r;
  };
  vector<int> h;
  vector<node> st;
  bool is_intersection(int l, int r, int ll, int rr) {
    if (r < ll || rr < l) return 0;
    return 1;
  }
  RMQ(vector<int> a) {
    h = a;
    st.resize(4 * h.size());
    build(0, h.size() - 1);
  }
  void build(int l, int r, int k = 0) {
    st[k].l = l, st[k].r = r;
    if (l == r) {
      st[k].mx = st[k].mn = l;
      return;
    }
    build(l, (l + r) / 2, 2 * k + 1);
    build((l + r) / 2 + 1, r, 2 * k + 2);
    if (h[st[2 * k + 1].mn] <= h[st[2 * k + 2].mn])
      st[k].mn = st[2 * k + 1].mn;
    else
      st[k].mn = st[2 * k + 2].mn;
    if (h[st[2 * k + 1].mx] >= h[st[2 * k + 2].mx])
      st[k].mx = st[2 * k + 1].mx;
    else
      st[k].mx = st[2 * k + 2].mx;
  }
  int minquery(int l, int r, int k = 0) {
    if (l > r) return 1000000000;
    int ll = st[k].l, rr = st[k].r, mid = (ll + rr) / 2;
    if (ll >= l && rr <= r) return st[k].mn;
    int ans = l;
    if (!(r < ll || mid < l)) ans = minquery(l, r, 2 * k + 1);
    if (!(r < mid + 1 || rr < l)) {
      if (h[ans] > h[minquery(l, r, 2 * k + 2)])
        ans = minquery(l, r, 2 * k + 2);
    }
    return ans;
  }
  int maxquery(int l, int r, int k = 0) {
    if (l > r) return -1000000000;
    int ll = st[k].l, rr = st[k].r, mid = (ll + rr) / 2;
    if (ll >= l && rr <= r) return st[k].mx;
    int ans = l;
    if (!(r < ll || mid < l)) ans = maxquery(l, r, 2 * k + 1);
    if (!(r < mid + 1 || rr < l)) {
      if (h[ans] < h[maxquery(l, r, 2 * k + 2)])
        ans = maxquery(l, r, 2 * k + 2);
    }
    return ans;
  }
  void update(int id, int val, int k = 0) {
    int l = st[k].l, r = st[k].r, mid = (l + r) / 2;
    if (l == r) {
      h[l] = val;
      return;
    }
    if (id >= l && id <= mid) update(id, val, 2 * k + 1);
    if (mid + 1 <= id && id <= r) update(id, val, 2 * k + 2);
    if (h[st[2 * k + 1].mn] <= h[st[2 * k + 2].mn])
      st[k].mn = st[2 * k + 1].mn;
    else
      st[k].mn = st[2 * k + 2].mn;
    if (h[st[2 * k + 1].mx] >= h[st[2 * k + 2].mx])
      st[k].mx = st[2 * k + 1].mx;
    else
      st[k].mx = st[2 * k + 2].mx;
  }
};
class LAZY {
 public:
  struct node {
    int l, r, lazy = 0;
    long long int lazyval = 0;
    long long int sum = 0;
  };
  vector<node> st;
  vector<int> h;
  LAZY(vector<int> a) {
    h = a;
    st.resize(4 * h.size());
    cst(0, h.size() - 1);
  }
  int intersectiontype1(int l, int r, int ll, int rr) {
    if (r < ll || rr < l) return 0;
    return 1;
  }
  void cst(int l, int r, int k = 0) {
    st[k].l = l, st[k].r = r;
    if (l == r) {
      st[k].sum = h[l];
      return;
    }
    cst(l, (l + r) / 2, 2 * k + 1);
    cst((l + r) / 2 + 1, r, 2 * k + 2);
    st[k].sum = st[2 * k + 1].sum + st[2 * k + 2].sum;
  }
  void shift(int k) {
    st[k].sum = (st[k].r - st[k].l + 1) * st[k].lazyval;
    if (st[k].l != st[k].r) {
      st[2 * k + 1].lazyval = st[k].lazyval;
      st[2 * k + 2].lazyval = st[k].lazyval;
      st[2 * k + 1].lazy = st[2 * k + 1].lazy = 1;
      st[2 * k + 2].lazy = st[2 * k + 2].lazy = 1;
    }
    st[k].lazyval = 0;
    st[k].lazy = 0;
  }
  long long int query(int l, int r, int k = 0) {
    if (st[k].lazy != 0) shift(k);
    int ll = st[k].l, rr = st[k].r, mid = (ll + rr) / 2;
    if (ll >= l && rr <= r) return st[k].sum;
    long long int ans = 0;
    if (intersectiontype1(ll, mid, l, r) == 1) ans = query(l, r, 2 * k + 1);
    if (intersectiontype1(1 + mid, rr, l, r) == 1)
      ans += query(l, r, 2 * k + 2);
    return ans;
  }
  void update(int l, int r, long long int x, int k = 0) {
    if (l > r) return;
    int ll = st[k].l, rr = st[k].r, mid = (ll + rr) / 2;
    if (ll >= l && rr <= r) {
      st[k].lazyval = x;
      st[k].lazy = 1;
      return;
    }
    if (st[k].lazy != 0) shift(k);
    if (st[k].l == st[k].r) return;
    if (intersectiontype1(ll, mid, l, r) == 1) update(l, r, x, 2 * k + 1);
    if (intersectiontype1(mid + 1, rr, l, r) == 1) update(l, r, x, 2 * k + 2);
    if (st[2 * k + 1].lazy != 0) shift(2 * k + 1);
    if (st[2 * k + 2].lazy != 0) shift(2 * k + 2);
    st[k].sum = st[2 * k + 1].sum + st[2 * k + 2].sum;
  }
  int lower_bound(int l, int r, int val) {
    while (l != r) {
      int mid = (l + r) / 2;
      if (query(mid, mid) >= val)
        r = mid;
      else {
        l = mid + 1;
        if (mid + 1 < h.size())
          if (query(mid + 1, mid + 1) > val) {
            l = mid;
            break;
          }
      }
    }
    return l;
  }
};
class span {
 public:
  vector<int> a;
  span(){};
  vector<int> max_left_border_without_equality() {
    int n = a.size();
    vector<int> ta, al(n);
    for (long long int i = 0; i < n; i++) {
      if (ta.size() == 0) {
        ta.push_back(i);
        al[i] = i;
      } else {
        while (a[i] > a[ta[ta.size() - 1]]) {
          ta.pop_back();
          if (ta.size() == 0) break;
        }
        if (ta.size() == 0) {
          ta.push_back(i);
          al[i] = 0;
        } else {
          al[i] = ta[ta.size() - 1] + 1;
          ta.push_back(i);
        }
      }
    }
    return al;
  }
  vector<int> max_left_border_with_equality() {
    int n = a.size();
    vector<int> ta, al(n);
    for (long long int i = 0; i < n; i++) {
      if (ta.size() == 0) {
        ta.push_back(i);
        al[i] = i;
      } else {
        while (a[i] >= a[ta[ta.size() - 1]]) {
          ta.pop_back();
          if (ta.size() == 0) break;
        }
        if (ta.size() == 0) {
          ta.push_back(i);
          al[i] = 0;
        } else {
          al[i] = ta[ta.size() - 1] + 1;
          ta.push_back(i);
        }
      }
    }
    return al;
  }
  vector<int> min_left_border_without_equality() {
    int n = a.size();
    vector<int> ta, al(n);
    for (long long int i = 0; i < n; i++) {
      if (ta.size() == 0) {
        ta.push_back(i);
        al[i] = i;
      } else {
        while (a[i] < a[ta[ta.size() - 1]]) {
          ta.pop_back();
          if (ta.size() == 0) break;
        }
        if (ta.size() == 0) {
          ta.push_back(i);
          al[i] = 0;
        } else {
          al[i] = ta[ta.size() - 1] + 1;
          ta.push_back(i);
        }
      }
    }
    return al;
  }
  vector<int> min_left_border_with_equality() {
    int n = a.size();
    vector<int> ta, al(n);
    for (long long int i = 0; i < n; i++) {
      if (ta.size() == 0) {
        ta.push_back(i);
        al[i] = i;
      } else {
        while (a[i] <= a[ta[ta.size() - 1]]) {
          ta.pop_back();
          if (ta.size() == 0) break;
        }
        if (ta.size() == 0) {
          ta.push_back(i);
          al[i] = 0;
        } else {
          al[i] = ta[ta.size() - 1] + 1;
          ta.push_back(i);
        }
      }
    }
    return al;
  }
  vector<int> max_right_border_without_equality() {
    int n = a.size();
    reverse(a.begin(), a.end());
    vector<int> ans = max_left_border_without_equality();
    reverse(ans.begin(), ans.end());
    for (long long int i = 0; i < n; i++) ans[i] = n - 1 - ans[i];
    reverse(a.begin(), a.end());
    return ans;
  }
  vector<int> max_right_border_with_equality() {
    int n = a.size();
    reverse(a.begin(), a.end());
    vector<int> ans = max_left_border_with_equality();
    reverse(ans.begin(), ans.end());
    for (long long int i = 0; i < n; i++) ans[i] = n - 1 - ans[i];
    reverse(a.begin(), a.end());
    return ans;
  }
  vector<int> min_right_border_without_equality() {
    int n = a.size();
    reverse(a.begin(), a.end());
    vector<int> ans = min_left_border_without_equality();
    reverse(ans.begin(), ans.end());
    for (long long int i = 0; i < n; i++) ans[i] = n - 1 - ans[i];
    reverse(a.begin(), a.end());
    return ans;
  }
  vector<int> min_right_border_with_equality() {
    int n = a.size();
    reverse(a.begin(), a.end());
    vector<int> ans = min_left_border_with_equality();
    reverse(ans.begin(), ans.end());
    for (long long int i = 0; i < n; i++) ans[i] = n - 1 - ans[i];
    reverse(a.begin(), a.end());
    return ans;
  }
};
class merge_sort_tree {
 public:
  long long int cnt(long long int x, vector<int> &arr) {
    long long int n = arr.size();
    vector<int>::iterator low, high;
    low = lower_bound(arr.begin(), arr.end(), x);
    if (low == (arr.end()) || *low != x) return 0;
    high = upper_bound(low, arr.end(), x);
    return high - low;
  }
  long long int get_last_smaller(vector<int> &v, int x) {
    long long int first = 0, last = v.size() - 1;
    while (first <= last) {
      long long int mid = (first + last) / 2;
      if (v[mid] >= x)
        last = mid - 1;
      else
        first = mid + 1;
    }
    return first - 1 < 0 ? -1 : first - 1;
  }
  struct node {
    int l, r;
    vector<int> arr;
  };
  vector<int> a;
  vector<node> st;
  merge_sort_tree(vector<int> b) {
    st.resize(4 * b.size());
    a = b;
    build(0, b.size() - 1);
  }
  void build(int l, int r, int k = 0) {
    st[k].l = l, st[k].r = r;
    for (int i = l; i < r + 1; i++) st[k].arr.push_back(a[i]);
    sort(st[k].arr.begin(), st[k].arr.end());
    if (l == r) return;
    build(l, (l + r) / 2, 2 * k + 1);
    build((l + r) / 2 + 1, r, 2 * k + 2);
  }
  bool intersection(int l, int r, int ll, int rr) {
    if (ll > r || l > rr) return 0;
    return 1;
  }
  long long int count_val_in_range(int l, int r, int t, int k = 0) {
    if (l > r) return 0;
    int ll = st[k].l, rr = st[k].r, mid = (ll + rr) / 2;
    if (ll >= l && rr <= r) return cnt(t, st[k].arr);
    long long int ans = 0;
    if (intersection(l, r, ll, mid) == 1)
      ans += count_val_in_range(l, r, t, 2 * k + 1);
    if (intersection(l, r, mid + 1, rr) == 1)
      ans += count_val_in_range(l, r, t, 2 * k + 2);
    return ans;
  }
  long long int count_vals_less_than_given_val(int l, int r, int t, int k,
                                               vector<node> &st) {
    if (l > r) return 0;
    int ll = st[k].l, rr = st[k].r, mid = (ll + rr) / 2;
    if (ll >= l && rr <= r) return get_last_smaller(st[k].arr, t) + 1;
    long long int ans = 0;
    if (intersection(l, r, ll, mid) == 1)
      ans += count_vals_less_than_given_val(l, r, t, 2 * k + 1, st);
    if (intersection(l, r, mid + 1, rr) == 1)
      ans += count_vals_less_than_given_val(l, r, t, 2 * k + 2, st);
    return ans;
  }
};
void DEBUG_ARR(vector<int> a) {
  for (long long int i = 0; i < a.size(); i++) cout << a[i] << " ";
  cout << "\n";
}
long long int tmod(long long int x, long long int m) { return (x % m + m) % m; }
long long int power(long long int x, long long int y) {
  long long int res = 1;
  while (y > 0) {
    if (y & 1) res = (res * x) % 1000000007;
    y = y >> 1;
    x = (x * x) % 1000000007;
  }
  if (res < 0) res += 1000000007;
  return res;
}
long long int modInverse(long long int a, long long int m) {
  long long int m0 = m;
  long long int y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    long long int q = a / m;
    long long int t = m;
    m = a % m, a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}
vector<int> tree[100001];
long long int contribution[100001], subtree_size[100001];
vector<long long int> wt[100001];
vector<int> parent(100001, 0);
int n;
void set_contribution(int u, int p) {
  subtree_size[u] = 1;
  for (auto x : tree[u]) {
    if (x == p) continue;
    set_contribution(x, u);
    parent[x] = u;
    subtree_size[u] += subtree_size[x];
    contribution[x] = (n - subtree_size[x]) * subtree_size[x];
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int q;
  cin >> q;
  while (q != 0) {
    q--;
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    if (k == 1) {
      cout << 0 << "\n";
      continue;
    }
    if (k == 2) {
      int f1 = false, f2 = false, f3 = false;
      for (long long int i = 0; i < n - 1; i++) {
        if (s[i] == 'R' && s[i + 1] == 'G')
          f1 = true;
        else if (s[i] == 'G' && s[i + 1] == 'B')
          f2 = true;
        else if (s[i] == 'B' && s[i + 1] == 'R')
          f3 = true;
      }
      if (f1 == 1 || f2 == 1 || f3 == 1)
        cout << 0 << "\n";
      else
        cout << 1 << "\n";
      continue;
    }
    int dp[n][3];
    for (long long int i = 0; i < n; i++)
      for (long long int j = 0; j < 3; j++) dp[i][j] = 0;
    for (long long int i = 0; i < k / 3; i++) {
      dp[0][0] +=
          (s[3 * i] != 'R') + (s[3 * i + 1] != 'G') + (s[3 * i + 2] != 'B');
      dp[0][1] +=
          (s[3 * i] != 'G') + (s[3 * i + 1] != 'B') + (s[3 * i + 2] != 'R');
      dp[0][2] +=
          (s[3 * i] != 'B') + (s[3 * i + 1] != 'R') + (s[3 * i + 2] != 'G');
    }
    int p = k / 3;
    if (k % 3 == 1) {
      dp[0][0] += (s[3 * p] != 'R');
      dp[0][1] += (s[3 * p] != 'G');
      dp[0][2] += (s[3 * p] != 'B');
    } else if (k % 3 == 2) {
      dp[0][0] += (s[3 * p] != 'R') + (s[3 * p + 1] != 'G');
      dp[0][1] += (s[3 * p] != 'G') + (s[3 * p + 1] != 'B');
      dp[0][2] += (s[3 * p] != 'B') + (s[3 * p + 1] != 'R');
    }
    for (long long int i = 0; i < k / 3; i++) {
      dp[1][0] +=
          (s[3 * i + 1] != 'R') + (s[3 * i + 2] != 'G') + (s[3 * i + 3] != 'B');
      dp[1][1] +=
          (s[3 * i + 1] != 'G') + (s[3 * i + 2] != 'B') + (s[3 * i + 3] != 'R');
      dp[1][2] +=
          (s[3 * i + 1] != 'B') + (s[3 * i + 2] != 'R') + (s[3 * i + 3] != 'G');
    }
    if (k % 3 == 1) {
      dp[1][0] += (s[3 * p + 1] != 'R');
      dp[1][1] += (s[3 * p + 1] != 'G');
      dp[1][2] += (s[3 * p + 1] != 'B');
    } else if (k % 3 == 2) {
      dp[1][0] += (s[3 * p + 1] != 'R') + (s[3 * p + 2] != 'G');
      dp[1][1] += (s[3 * p + 1] != 'G') + (s[3 * p + 2] != 'B');
      dp[1][2] += (s[3 * p + 1] != 'B') + (s[3 * p + 2] != 'R');
    }
    for (long long int i = 0; i < k / 3; i++) {
      dp[2][0] +=
          (s[3 * i + 2] != 'R') + (s[3 * i + 3] != 'G') + (s[3 * i + 4] != 'B');
      dp[2][1] +=
          (s[3 * i + 2] != 'G') + (s[3 * i + 3] != 'B') + (s[3 * i + 4] != 'R');
      dp[2][2] +=
          (s[3 * i + 2] != 'B') + (s[3 * i + 3] != 'R') + (s[3 * i + 4] != 'G');
    }
    if (k % 3 == 1) {
      dp[2][0] += (s[3 * p + 2] != 'R');
      dp[2][1] += (s[3 * p + 2] != 'G');
      dp[2][2] += (s[3 * p + 2] != 'B');
    } else if (k % 3 == 2) {
      dp[2][0] += (s[3 * p + 2] != 'R') + (s[3 * p + 3] != 'G');
      dp[2][1] += (s[3 * p + 2] != 'G') + (s[3 * p + 3] != 'B');
      dp[2][2] += (s[3 * p + 2] != 'B') + (s[3 * p + 3] != 'R');
    }
    char at[3] = {'R', 'G', 'B'}, mp[3];
    for (long long int i = 0; i < 3; i++) mp[i] = at[(i + k) % 3];
    for (long long int i = 3; i < n - k + 1; i++) {
      dp[i][0] = dp[i - 3][0] + (s[i + k - 3] != mp[0]) +
                 (s[i + k - 2] != mp[1]) + (s[i + k - 1] != mp[2]) -
                 (s[i - 3] != 'R') - (s[i - 2] != 'G') - (s[i - 1] != 'B');
      dp[i][1] = dp[i - 3][1] + (s[i + k - 3] != mp[1]) +
                 (s[i + k - 2] != mp[2]) + (s[i + k - 1] != mp[0]) -
                 (s[i - 3] != 'G') - (s[i - 2] != 'B') - (s[i - 1] != 'R');
      dp[i][2] = dp[i - 3][2] + (s[i + k - 3] != mp[2]) +
                 (s[i + k - 2] != mp[0]) + (s[i + k - 1] != mp[1]) -
                 (s[i - 3] != 'B') - (s[i - 2] != 'R') - (s[i - 1] != 'G');
    }
    int ans = 1000000000;
    for (long long int i = 0; i < n - k + 1; i++) ans = min(ans, dp[i][0]);
    for (long long int i = 0; i < n - k + 1; i++) ans = min(ans, dp[i][1]);
    for (long long int i = 0; i < n - k + 1; i++) ans = min(ans, dp[i][2]);
    cout << ans << "\n";
  }
  return 0;
}

```