Do phải học tin quá nhiều nên mặc dù đã học tới lớp ~12~ nhưng việc thuộc cả bảng chữ cái tiếng anh là công việc vô cùng khó khăn với Hoàng, bởi thế cậu luôn bị trêu trọc trong giờ tiếng anh. Không muốn chịu mất mặt mãi (đặc biệt trước gấu), Hoàng đã lên kế hoạch tập luyện riêng cho mình ...

Mỗi ngày cậu chọn ra một số nguyên dương ~k~, rồi cả ngày hôm đó cậu chỉ viết ~k~ chữ cái đầu tiên của bảng chữ cái tiếng anh thường lên một tờ giấy, tạo thành một xâu ~S~, với hy vọng có thể nhớ đủ ~k~ chữ cái đó. Rất vui sướng với tờ giấy có xâu ~S~, cậu liền đem nó cho Khải xem thành quả một ngày viết của mình.

Sau một hồi ngắm nghía tờ giấy, Khải bỗng nảy ra câu hỏi: "Liệu có bao nhiêu đoạn con gồm các kí tự liên tiếp của ~S~ sao cho số lần xuất hiện của các chữ cái từ ~1~ tới ~k~ là bằng nhau trong đoạn đó" (xem test cho dễ hiểu :D).

Với đôi mắt cú vọ có thể nhìn hàng nghìn chữ cái trong một giây và cái đầu tính toán nhanh hơn một chiếc máy tính điện tử, Hoàng đã nhanh chóng đưa ra đáp án cho Khải. Vốn không tin vào kết quả của Hoàng và cho rằng Hoàng đưa ra kết quả bừa để lừa mình, bởi vậy Khải cần bạn tính thật nhanh kết quả bài toán để có thể so sánh với kết quả của Hoàng. Help him!!.

Input

Dòng ~1~: Số nguyên ~T~, số test thử nghiệm ~(1 \leq T \leq 10)~.

~T~ bộ test tiếp theo có dạng:

Dòng ~1~: Gồm hai số nguyên ~N~ và ~k~ ~(1 \leq N \leq 10^{5}~, ~1 \leq k \leq 7)~.

Dòng ~2~: Một xâu ~S~ có độ dài ~N~, đảm bảo ~S~ chỉ có ~k~ chữ cái đầu tiên trong bảng chữ cái tiếng anh thường.

Output

Gồm ~T~ dòng là kết quả ứng với ~T~ bộ test.

Giới hạn

~25\%~ số test có ~k \leq 2~.

Sample Input

1
4 2
abab

Sample Output

4

Note

Giải thích: các đoạn thỏa mãn là ~[1,2], [2,3], [3,4] và [1,4]~.