#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void getar(T a, int n, int m) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; ++j) {
      scanf("%d", &a[i][j]);
    }
}
inline void getar(int *a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%d", a + ii);
  }
}
inline void getar(pair<int, int> *a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("d", &a[ii].first, &a[ii].second);
  }
}
inline void getar(long long *a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%I64d", a + ii);
  }
}
inline void getv(vector<int> &a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%d", &a[ii]);
  }
}
inline void getv(vector<long long> &a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%I64d", &a[ii]);
  }
}
inline void getv(vector<pair<int, int> > &a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%d", &a[ii].first, &a[ii].second);
  }
}
inline void getv(vector<pair<long long, long long> > &a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%I64d", &a[ii].first, &a[ii].second);
  }
}
inline void getvv(vector<vector<int> > &a, int n, int m) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; ++j) {
      scanf("%d", &a[i][j]);
    }
}
inline void printa(int *a, int i, int j) {
  for (int ii = i; ii <= j; ii++) {
    printf("%d ", a[ii]);
  }
}
inline void printa(long long *a, int i, int j) {
  for (int ii = i; ii <= j; ii++) {
    printf("%I64d ", a[ii]);
  }
}
inline void printv(vector<int> &a, int i, int j) {
  for (int ii = i; ii <= j; ii++) {
    printf("%d ", a[ii]);
  }
}
inline void printv(vector<long long> &a, int n, int i, int j) {
  for (int ii = i; ii <= j; ii++) {
    printf("%I64d ", a[ii]);
  }
}
inline long long max(long long a, long long b) { return (a > b) ? a : b; }
inline int max(int a, int b) { return (a > b) ? a : b; }
inline double max(double a, double b) { return (a > b) ? a : b; }
inline long long max(long long a, long long b, long long c) {
  return max(a, max(b, c));
}
inline int max(int a, int b, int c) { return max(a, max(b, c)); }
inline double max(double a, double b, double c) { return max(a, max(b, c)); }
inline long long min(long long a, long long b) { return (a < b) ? a : b; }
inline int min(int a, int b) { return (a < b) ? a : b; }
inline double min(double a, double b) { return (a < b) ? a : b; }
inline long long min(long long a, long long b, long long c) {
  return min(a, min(b, c));
}
inline int min(int a, int b, int c) { return min(a, min(b, c)); }
inline double min(double a, double b, double c) { return min(a, min(b, c)); }
inline long long pow(long long x, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res *= x;
    x *= x;
    n >>= 1;
  }
  return res;
}
inline long long powmod(long long x, long long n, long long _mod) {
  long long res = 1;
  while (n) {
    if (n & 1) res = (res * x) % _mod;
    x = (x * x) % _mod;
    n >>= 1;
  }
  return res;
}
inline long long gcd(long long a, long long b) {
  long long t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline int gcd(int a, int b) {
  int t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline long long lcm(int a, int b) { return a / gcd(a, b) * (long long)b; }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long gcd(long long a, long long b, long long c) {
  return gcd(gcd(a, b), c);
}
inline int gcd(int a, int b, int c) { return gcd(gcd(a, b), c); }
inline long long lcm(long long a, long long b, long long c) {
  return lcm(lcm(a, b), c);
}
inline long long lcm(int a, int b, int c) {
  return lcm(lcm(a, b), (long long)c);
}
inline int bits_count(int v) {
  v = v - ((v >> 1) & 0x55555555);
  v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
  return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
inline int bits_count(long long v) {
  long long t = v >> 32;
  long long p = (v & ((1LL << 32) - 1));
  return bits_count(t) + bits_count(p);
}
inline bool ispow2(int x) { return (x != 0 && (x & (x - 1)) == 0); }
const char nl = '\n';
string s;
int n, k;
string rgb;
vector<vector<int> > dp;
void intialize_dp() {
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < k; j++) dp[i][0] += (s[j] != rgb[(j + i) % 3]);
}
void solve() {
  rgb = "RGB";
  cin >> n >> k;
  cin >> s;
  dp = vector<vector<int> >(3, vector<int>(n, 0));
  intialize_dp();
  bool prev_first, cur_last;
  int ans = min(dp[0][0], dp[1][0], dp[2][0]);
  for (int i = 0; i < 3; i++)
    for (int j = 1; j < n - k + 1; j++) {
      prev_first = (s[j - 1] != rgb[(j - 1 + i) % 3]);
      cur_last = (s[j + k - 1] != rgb[(j + i + k - 1) % 3]);
      dp[(i + j) % 3][j] = dp[(i + j - 1) % 3][j - 1] + cur_last - prev_first;
      ans = min(ans, dp[(i + j) % 3][j]);
    }
  cout << ans << nl;
}
int main() {
  clock_t clk = clock();
  cerr << "Hey P..\n";
  int t;
  cin >> t;
  while (t--) solve();
  cerr << "Look at the sky.\n";
  cerr << "Time (in ms): " << (double)(clock() - clk) * 1000.0 / CLOCKS_PER_SEC
       << '\n';
  return 0;
}

### Prompt

Generate a CPP solution to the following problem:

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>
using namespace std;
template <class T>
inline void getar(T a, int n, int m) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; ++j) {
      scanf("%d", &a[i][j]);
    }
}
inline void getar(int *a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%d", a + ii);
  }
}
inline void getar(pair<int, int> *a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("d", &a[ii].first, &a[ii].second);
  }
}
inline void getar(long long *a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%I64d", a + ii);
  }
}
inline void getv(vector<int> &a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%d", &a[ii]);
  }
}
inline void getv(vector<long long> &a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%I64d", &a[ii]);
  }
}
inline void getv(vector<pair<int, int> > &a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%d", &a[ii].first, &a[ii].second);
  }
}
inline void getv(vector<pair<long long, long long> > &a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%I64d", &a[ii].first, &a[ii].second);
  }
}
inline void getvv(vector<vector<int> > &a, int n, int m) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; ++j) {
      scanf("%d", &a[i][j]);
    }
}
inline void printa(int *a, int i, int j) {
  for (int ii = i; ii <= j; ii++) {
    printf("%d ", a[ii]);
  }
}
inline void printa(long long *a, int i, int j) {
  for (int ii = i; ii <= j; ii++) {
    printf("%I64d ", a[ii]);
  }
}
inline void printv(vector<int> &a, int i, int j) {
  for (int ii = i; ii <= j; ii++) {
    printf("%d ", a[ii]);
  }
}
inline void printv(vector<long long> &a, int n, int i, int j) {
  for (int ii = i; ii <= j; ii++) {
    printf("%I64d ", a[ii]);
  }
}
inline long long max(long long a, long long b) { return (a > b) ? a : b; }
inline int max(int a, int b) { return (a > b) ? a : b; }
inline double max(double a, double b) { return (a > b) ? a : b; }
inline long long max(long long a, long long b, long long c) {
  return max(a, max(b, c));
}
inline int max(int a, int b, int c) { return max(a, max(b, c)); }
inline double max(double a, double b, double c) { return max(a, max(b, c)); }
inline long long min(long long a, long long b) { return (a < b) ? a : b; }
inline int min(int a, int b) { return (a < b) ? a : b; }
inline double min(double a, double b) { return (a < b) ? a : b; }
inline long long min(long long a, long long b, long long c) {
  return min(a, min(b, c));
}
inline int min(int a, int b, int c) { return min(a, min(b, c)); }
inline double min(double a, double b, double c) { return min(a, min(b, c)); }
inline long long pow(long long x, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res *= x;
    x *= x;
    n >>= 1;
  }
  return res;
}
inline long long powmod(long long x, long long n, long long _mod) {
  long long res = 1;
  while (n) {
    if (n & 1) res = (res * x) % _mod;
    x = (x * x) % _mod;
    n >>= 1;
  }
  return res;
}
inline long long gcd(long long a, long long b) {
  long long t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline int gcd(int a, int b) {
  int t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline long long lcm(int a, int b) { return a / gcd(a, b) * (long long)b; }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long gcd(long long a, long long b, long long c) {
  return gcd(gcd(a, b), c);
}
inline int gcd(int a, int b, int c) { return gcd(gcd(a, b), c); }
inline long long lcm(long long a, long long b, long long c) {
  return lcm(lcm(a, b), c);
}
inline long long lcm(int a, int b, int c) {
  return lcm(lcm(a, b), (long long)c);
}
inline int bits_count(int v) {
  v = v - ((v >> 1) & 0x55555555);
  v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
  return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
inline int bits_count(long long v) {
  long long t = v >> 32;
  long long p = (v & ((1LL << 32) - 1));
  return bits_count(t) + bits_count(p);
}
inline bool ispow2(int x) { return (x != 0 && (x & (x - 1)) == 0); }
const char nl = '\n';
string s;
int n, k;
string rgb;
vector<vector<int> > dp;
void intialize_dp() {
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < k; j++) dp[i][0] += (s[j] != rgb[(j + i) % 3]);
}
void solve() {
  rgb = "RGB";
  cin >> n >> k;
  cin >> s;
  dp = vector<vector<int> >(3, vector<int>(n, 0));
  intialize_dp();
  bool prev_first, cur_last;
  int ans = min(dp[0][0], dp[1][0], dp[2][0]);
  for (int i = 0; i < 3; i++)
    for (int j = 1; j < n - k + 1; j++) {
      prev_first = (s[j - 1] != rgb[(j - 1 + i) % 3]);
      cur_last = (s[j + k - 1] != rgb[(j + i + k - 1) % 3]);
      dp[(i + j) % 3][j] = dp[(i + j - 1) % 3][j - 1] + cur_last - prev_first;
      ans = min(ans, dp[(i + j) % 3][j]);
    }
  cout << ans << nl;
}
int main() {
  clock_t clk = clock();
  cerr << "Hey P..\n";
  int t;
  cin >> t;
  while (t--) solve();
  cerr << "Look at the sky.\n";
  cerr << "Time (in ms): " << (double)(clock() - clk) * 1000.0 / CLOCKS_PER_SEC
       << '\n';
  return 0;
}

```