Count Distinct Substrings of Fixed Length

You are given an integer T and then T test cases. For each test case, you are provided with a string S and an integer k.

Your task is to calculate the number of distinct substrings of S that have exactly k characters.

In mathematical terms, for a given string \(S\) of length \(n\) and an integer \(k\) with \(1 \leq k \leq n\), you need to compute the cardinality of the set:

[ { S[i:i+k] \mid 0 \leq i \leq n - k } ]

Print the result for each test case on a new line.

inputFormat

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

• The first line contains an integer T denoting the number of test cases.
• For each test case, the first line contains a non-empty string S (consisting of lowercase letters) and the second line contains an integer k (with 1 ≤ k ≤ |S|).

outputFormat

For each test case, output a single integer on a new line representing the number of distinct substrings of length k in S.

## sample

2
abcabc
3
abcd
2

3
3

</p>