Distinct Substrings Count

You are given a string S and an integer K. Your task is to determine the number of distinct substrings of length \(K\) that appear in S. If K is 0 or if \(K > |S|\) (where \(|S|\) denotes the length of the string), then the result is 0.

Example:

Input:
abcd
2
There are 3 distinct substrings of length 2: "ab", "bc", and "cd".
Output:
3

</p>

The problem requires that you process multiple test cases. The input begins with an integer T, the number of test cases. For each test case, the first line contains the string S (which may be empty), and the second line contains the integer K.

Note: All formulas are rendered in \( \LaTeX \) format. For instance, \(|S|\) represents the length of string S.

inputFormat

The first line of input contains a single integer T, the number of test cases. For each test case, there are two lines:

1. The first line contains the string S (possibly empty).
2. The second line contains an integer K.

It is guaranteed that K is a non-negative integer.

outputFormat

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

## sample

1
abcd
2

3

</p>