String

Accepts: 115
Submissions: 264
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Problem Description
There is a string $S$.$S$ only contain lower case English character.$(10 \leq length(S) \leq 1,000,000)$ How many substrings there are that contain at least $k(1 \leq k \leq 26)$ distinct characters?
Input
There are multiple test cases. The first line of input contains an integer $T (1\leq T\leq 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 \leq k \leq 26)$.
Output
For each test case, output the number of substrings that contain at least $k$ dictinct characters.
Sample Input
2
abcabcabca
4
abcabcabcabc
3
Sample Output
0
55