Abhishek is fond of playing cricket very much. One morning, he is playing cricket with his friends. Abhishek is a right-hand batsman

.He has to face all types of balls either good or bad. There are total 26 balls in the game and each ball is represented

by one of the following two ways:-
1. "g" denotes a good ball.
2. "b" denotes a bad ball.
All 26 balls are represented by lower case letters (a,b,.....z).
Balls faced by Abhishek are represented as a string s, all the characters of which are lower case i.e, within 26 above mentioned balls.
A substring s[l...r] (1≤l≤r≤|s|) of string s=s1s2...s|s| (where |s| is the length of string s) is string slsl+1...sr.
The substring s[l...r] is good, if among the letters slsl+1...sr, there are at most k bad ones (refer sample explanation ).
Your task is to find out the number of distinct good substrings for the given string s. Two substrings s[x...y] and s[p...q] are considered distinct if their contents are different, i.e. s[x...y]≠s[p...q].

-----Input Format-----
First Line contains an integer T, number of test cases. For each test case, first line contains a string - a sequence of balls faced by Abhishek.

And, next line contains a string of characters "g" and "b" of length 26 characters. If the ith character of this string equals "1", then the i-th English letter is good, otherwise it's bad. That is, the first character of this string corresponds to letter "a", the second one corresponds to letter "b" and so on.

And, the third line of the test case consists of a single integer k (0≤k≤|s|) — the maximum acceptable number of bad characters in a good substring.

-----Output Format -----
For each test case, print a single integer — the number of distinct good substrings of string s.

-----Constraints-----
- 1<=T<=1000
- 1<=|s|<=2000
- 0<=k<=|s|

-----Subtasks-----
Subtask 1 : 20 Points
- 1<=T<=10
- 1<=|s|<=20
- 0<=k<=|s|
Subtask 2 : 80 Points
Original Constraints
Sample Input
2
ababab
bgbbbbbbbbbbbbbbbbbbbbbbbb
1
acbacbacaa
bbbbbbbbbbbbbbbbbbbbbbbbbb
2
Sample Output
5
8

Explanation
In the first test case there are following good substrings: "a", "ab", "b", "ba", "bab".

In the second test case there are following good substrings: "a", "aa", "ac", "b", "ba", "c", "ca", "cb".

见题面

见题面