Substring Permutation

You are given a string S of length N and an array of strings ARR. All the strings in ARR are of the same length K. Your task is to find the number of such sub-strings in the string 'S' that is the concatenation of all the strings of ARR in some order.

For example :

Let ARR = [hot, dog] and S = "hotdoghot", there are two sub-strings that can be obtained by permutation of ARR starting from index 0 -> ‘hotdog’ and starting from the index 3 -> ‘doghot’.

Note :

1. An string C is a substring of string S if it can be obtained by deletion of several characters(possibly zero) from the beginning and the end from a string S.
2. The substring must contain all the strings in ARR only once and without any extra intervening character.

Input Format :

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

The first line of each test case contains three single space-separated integers ‘N’, ‘M’, ‘K’ denoting the size of the string S, length of the array/list ARR and length of each string in ARR. 

The second line of each test case contains string S.

The third line of each test case contains ‘M’ space-separated strings, denoting the elements of the array ARR.

Output Format :

For each test case print the number of substrings that can be formed by some permutation of ARR. 

Output for each test case is printed in a separate line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 1000
1 <= M <= 10
1 <= K <= 100      
String S and all the strings in ARR contain only lowercase English letters.

Time Limit: 1 sec