Kaninho tập đếm với xâu

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
jumptozero
Dạng bài
Điểm: 400 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

\(Kaninho\) được cho một xâu \(S\) chỉ gồm các kí tự latin thường, và nhiệm vụ của anh ấy là đếm xem có bao nhiêu xâu con (gồm những phần tử liên tiếp) thoả mãn số lần xuất hiện của mỗi kí tự trong xâu con đó không lớn hơn \(K\)

Input

  • Dòng thứ nhất chứa số \(t(1\le t\le 100)\) - Thể hiện số testcase

  • \(t\) test tiếp theo, mỗi dòng chứa một test có dạng như sau:

  • Dòng thứ nhất chứa xâu \(S\) - Biết rằng, độ dài xâu \(S\) không vượt quá \(10^5\)

  • Dòng thứ hai chứa số \(K\) \((1\le K\le 10^5)\)

Output

  • Ứng với mỗi testcase, in ra đáp án cần tìm

Scoring

  • Subtask \(1\) (\(37.5\%\) số điểm): \(1\) \(\le\) |S| \(\le 20\) ,\(1\) \(\le\) \(K\) \(\le 5\).

  • Subtask \(2\) (\(62.5\%\) số điểm): không có điều kiện gì thêm.

Example

Test 1

Input 
1
abc
1
Output 
6
Note
  • Ứng với testcase \(1\): Ta có \(6\) xâu con thoả mãn là : \(a,b,c,ab,bc,abc\)

Bình luận