Vlad đang lên kế hoạch tổ chức m vòng thi vào tháng sau. Mỗi vòng thi sẽ có một bài toán thuộc mức độ khó A, B, C, D, E, F hoặc G.

Vlad đã có một ngân hàng gồm n bài toán, trong đó bài toán thứ i có mức độ khó là a_i. Có thể là không đủ các bài toán này, vì vậy Vlad có thể cần phải tạo thêm một vài bài toán nữa.

Vlad muốn tạo thêm càng ít bài toán càng tốt, vì vậy anh ấy yêu cầu bạn tìm số lượng tối thiểu các bài toán cần tạo ra để có đủ bài toán cho m vòng thi.

Ví dụ, nếu m = 1, n = 10, a = “BGECDCBDED”, thì anh ấy cần tạo thêm hai bài toán: một bài toán thuộc mức độ khó A và một bài toán thuộc mức độ khó F.

Input

Dòng đầu tiên chứa một số nguyên t (1 ≤ t ≤ 1000) – số lượng trường hợp kiểm tra.

Dòng đầu tiên của mỗi trường hợp kiểm tra chứa hai số nguyên n và m (1 ≤ n ≤ 50, 1 ≤ m ≤ 5) – số lượng bài toán trong ngân hàng và số lượng vòng thi sắp tới, tương ứng.

Dòng thứ hai của mỗi trường hợp kiểm tra chứa một chuỗi a có độ dài n ký tự từ A đến G – mức độ khó của các bài toán trong ngân hàng.

Output

Với mỗi trường hợp kiểm tra, xuất ra một số nguyên duy nhất – số lượng tối thiểu các bài toán cần tạo thêm để có đủ bài toán cho m vòng thi.

Example