Count with K different characters

You are given a string ‘STR’ of lowercase alphabets and an integer K. Your task is to count all the possible substrings that are not necessarily distinct but should have exactly K distinct characters.

For example:

'STR' = “abcad” and K = 2. 
We can see that the substrings {ab, bc, ca, ad} are the only substrings with 2 distinct characters. Therefore, the answer will be 4.    

Input format :

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

The first and the only line of each test case contains a string ‘STR’.

The second line of each test case contains a single integer K.

Output format :

For each test case, in a separate line, return a single integer which is the count of all possible substrings having exactly K distinct characters.

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= |STR| <= 3*10^3
1 <= K <= 26

Time Limit: 1 second