Maximum Distinct Substrings

You are given a string S and an integer K. Your task is to calculate the maximum number of distinct substrings of length K that can be extracted from S.

To be more formal, given a string \( S \) and an integer \( K \), you must determine the value:

\[ \text{answer} = |\{ S[i : i+K] \mid 0 \leq i \leq |S| - K \}|, \]

where \( S[i : i+K] \) denotes the substring of \( S \) starting at index \( i \) with length \( K \). If \( K \) is greater than the length of \( S \), the answer is 0.

The input contains multiple test cases. For each test case, output the result on a separate line.

inputFormat

The first line of input contains an integer T denoting the number of test cases.

Each of the following T lines contains a test case consisting of a string S and an integer K separated by whitespace.

Example:

2
abcabcab 3
abcdef 2

outputFormat

For each test case, output a single line containing the maximum number of distinct substrings of length K that can be extracted from the string S.

Example:

3
5

## sample

2
abcabcab 3
abcdef 2

3
5

</p>