Count Good Substrings

Given a string \( s \) and an integer \( k \), a substring of \( s \) is called good if all its characters are distinct. Your task is to count the number of good substrings of length \( k \) in \( s \).

A substring is defined as a contiguous sequence of characters from \( s \). For example, if \( s = \texttt{abcabc} \) and \( k = 3 \), the good substrings are \( \texttt{abc} \), \( \texttt{bca} \), \( \texttt{cab} \), and \( \texttt{abc} \) again, resulting in a count of 4. Note that substrings are distinguished by their starting positions.

inputFormat

The input is read from stdin and has the following format:

T
s₁
k₁
s₂
k₂
...
s_T
k_T

Where:

• \( T \) is an integer representing the number of test cases.
• Each test case consists of two lines. The first line contains a string \( s \) and the second line contains an integer \( k \).

outputFormat

For each test case, output a single integer on a new line representing the number of good substrings of length \( k \) in the string \( s \). The output is printed to stdout.

## sample

1
abcabc
3

4

</p>