Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

HBTLAST - HBTLAST

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 cho mình riêng.... 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≤T≤10).

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

Dòng 1: Gồm hai số nguyên N và k (1≤N≤105, 1≤k≤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.

Example

Input:

1

4 2

abab

Output:

4

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

Chú ý: 25% số test có k≤2.


Được gửi lên bởi:Thương
Ngày:2014-10-31
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2014-11-01 15:15:46 Lollipop
quên bỏ int64 :(

Last edit: 2014-11-01 15:19:02
2014-11-01 15:07:10 Lollipop
ad xem e bị lỗi gì vậy ad, e text mãi thấy kq đúng mà k biết sao đk 55
2014-10-31 15:04:09 LOVE VNOI
Bài tập tự chém cuối cùng add lên vnoi, phải chia tay mọi người, buồn quá :3

Last edit: 2014-11-01 07:02:13
2014-10-31 14:53:57 TClTY
sao lam dk n=10^5 he
2014-10-31 13:19:26 Hướng Thái Dương
chắc nó cx chừa mình ra >:(
2014-10-31 12:02:02 Mew.
chắc nó chừa mình ra :v
PS: Chính là anh =)))))))))

Last edit: 2014-10-31 12:23:07
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.