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.

2
abcabcabca
4
abcabcabcabc
3

0
55