Count Distinct Substrings of Length K

You are given a series of test cases. For each test case, you are given an integer \(K\) and a string \(S\). Your task is to compute the number of distinct substrings of \(S\) having length exactly \(K\). A substring is a contiguous segment of characters in the string.

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

For example, consider \(K=3\) and \(S=\) "abcabc". The distinct substrings of length 3 are "abc", "bca", and "cab", so the output is 3.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer \(T\) representing the number of test cases. The following lines contain the description of each test case in the following format:

• The first line of each test case contains an integer \(K\) (the required substring length).
• The second line of each test case contains the string \(S\). Note that \(S\) can be empty.

outputFormat

For each test case, output a single integer on a new line which is the number of distinct substrings of length \(K\) in the string \(S\).

## sample

1
3 abcabc

3

</p>