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?
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)
For each test case, output the number of substrings that contain at least k dictinct characters.
2 abcabcabca 4 abcabcabcabc 3