Sacchi and Maurya are String lovers. They love to solve problems on strings. So our born-talented Priyun decided to ask them a problem on strings. He gave them a string of size S which consists of only small English letters. According to Priyun some of the alphabets are “Nice” and rest all are “Eww”. Now Priyun has a tolerance level of X “Eww”.
Priyun wants to know the distinct substrings of the given string which he can tolerate.
Even Sacchi and Maurya is finding it difficult to solve. So help them.

Input

The input file consists of several cases T (1<=T<=10).
The first line of each test case consists of a string S, [Size of S is <=2000].
S consists of only lowercase English Letters.
Next line contains the number P[0<=P<=26], the number of “Nice” Alphabets.
Next P lines contains an Alphabet that is Nice. All the P characters are distinct and it is between [a,z].
Next line contains an Integer X i.e. the tolerance level of Priyun.

Output

Print a single integer for each testcase i.e  the number of distinct substrings that Priyun can tolerate.

Example

Input:
1
bbbbbbbbba
1
b
0

Output:
9