Count Substrings with Exactly K Distinct Characters

You are given a string \( S \) and an integer \( K \). Your task is to count the number of substrings of \( S \) that contain exactly \( K \) distinct characters.

A substring is a contiguous sequence of characters within the string. For a given substring \( S[i \ldots j] \), it is considered valid if the number of unique characters in it is exactly \( K \). For example, for \( S = \texttt{ababc} \) and \( K = 2 \), one valid substring is \( \texttt{ab} \) and there are a total of 7 valid substrings.

Note: Use efficient algorithms, as the length \( N \) of the string can be large (up to \( 10^4 \)).

inputFormat

The input is read from standard input (stdin) and consists of multiple test cases.

The first line contains an integer \( T \) representing the number of test cases. Each of the following \( T \) lines contains a test case in the following format:

N K S

where:

• \( N \) is the length of the string \( S \) (it can be ignored since \( S \)'s length is inherent).
• \( K \) is the number of distinct characters required.
• \( S \) is the input string consisting of lowercase English letters.

outputFormat

For each test case, output a single integer on a new line representing the number of substrings of \( S \) that contain exactly \( K \) distinct characters. The output is written to standard output (stdout).

## sample

2
5 2 ababc
4 1 aaaa

7
10

</p>