Rachel works at a big fashion organization. There is a big event coming up and she has to select dresses for an exhibition.
She has N dresses numbered 1 to N. There are total 62 types of dresses, each represented by a different alphanumeric character (a-z, A-Z, 0-9). The N dresses are represented by a string S of length N of alphanumeric characters. The ith character of S denotes the type of the ith dress. Rachel will select two integers, A and B such that 1 <= A <= B <= N and take the dresses numbered from A to B to the exhibition.
Out of the 62 dress types, K dress types are special. Find the number of values of A and B possible such that the total number of special dresses of any type selected are atleast L and atmost R.
Input:
The first line of the input contains T, the number of test cases. The first line of each test case contains N, K, L and R. The second line of each test case contains the string of length N that denotes the type of the N dresses. The third line contains another string of length K, denoting the types of the special dresses
Output:
For each test case, output the number of ways to select A and B.
Constraints:
- 1 <= T <= 100
- 1 <= N <= 104
- 1 <= K <= 62
- 0 <= L <= R <= N
- S contains alphanumeric characters: (a-z, A-Z and 0-9)