An đượ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

Example

Ví dụ:

Input

1
abc
1

Output

6

Note

• Ta có \(6\) xâu con thoả mãn là : \(a,b,c,ab,bc,abc\)

Ràng buộc

• 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.