Problem I: Interesting String

Problem I: Interesting String

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 19  Solved: 8
[Submit] [Status] [Web Board] [Creator:]

Description

CET-4 is really difficult, but Zser must pass CET-4 this time, just as he can successfully AC this question.
Zser have a string s,s only contain lower English character. Now, Zser want to calculat how many substrings there are that contain at least k(1≤k≤26) distinct characters?

Input

The first line of input contains an integer T(T≤10) indicating the number of test cases.
For each test case: The first line contains string s, The second line contains a integer K(1 <= K <= 26)

Output

For each test case, output the number of substrings that contain at least k dictinct characters.

Sample Input Copy

2
abcabcabca
4
abcabcabcabc
3

Sample Output Copy

0
55