Xâu con RGB (bản khó)

Cho xâu $s$ độ dài $n$ chỉ gồm các ký tự R, G, B và số nguyên $k$.

Bạn cần thay đổi số ký tự ít nhất có thể trong $s$ sao cho $s$ chứa một xâu con liên tiếp độ dài $k$ đồng thời cũng là xâu con liên tiếp của xâu vô hạn RGBRGBRGB....

Một xâu $a$ là xâu con liên tiếp của xâu $b$ nếu tồn tại chỉ số $i$ sao cho $a_1=b_i,a_2=b_{i+1},\dots ,a_{|a|}=b_{i+|a|-1}$.

Bạn phải xử lý $q$ truy vấn độc lập nhau.

Dữ liệu vào

• Dòng đầu chứa số nguyên $q$ — số lượng truy vấn.
• Với mỗi truy vấn:
  • Dòng đầu chứa hai số nguyên $n$ và $k$ ($1\le k\le n\le 2·{10}^5$).
  • Dòng thứ hai chứa xâu $s$ độ dài $n$ chỉ gồm các ký tự R, G, B.

Dữ liệu ra

In ra $q$ dòng, mỗi dòng là đáp án của một truy vấn — số ký tự ít nhất cần thay đổi.

Ràng buộc

• $1\le q\le 2·{10}^5$
• $1\le k\le n\le 2·{10}^5$
• Tổng $n$ trên toàn bộ truy vấn không vượt quá $2·{10}^5$.

Ví dụ