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.