Distinct Substrings

You are given a string S and an integer K. Your task is to compute the number of distinct substrings of S of length K.

Formally, given a string \( S \) and an integer \( K \), find the number of unique substrings \( T \) such that \( T = S[i:i+K] \) for some valid index \( i \), and \( |T| = K \).

If \( K \) is greater than the length of \( S \), the answer is 0.

For example, for S = "abcabc" and K = 3, the distinct substrings of length 3 are "abc", "bca", and "cab", so the answer is 3.

inputFormat

The input is given via stdin and consists of multiple test cases. The first line contains an integer T, the number of test cases. Each test case consists of two lines:

1. The first line contains the string S.
2. The second line contains an integer K.

Note that the string S consists only of lowercase English letters.

outputFormat

For each test case, print a single line to stdout containing the number of distinct substrings of length K in S.

## sample

2
abcabc
3
aaaaaa
2

3
1

</p>