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".

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "import sys\nfor _ in range(0,eval(input())):   \n    d,inp,mp,n,q=set(),list(map(ord,list(sys.stdin.readline().strip()))),[x=='g' for x in list(sys.stdin.readline().strip())],eval(input()),ord('a')\n    for i in range(0,len(inp)):\n        nn,h=n,0\n        for j in range(i,len(inp)):\n                if ( (mp[inp[j]-q]) or  nn>0 ):\n                    if(mp[inp[j]-q] == False ):                \n                        nn=nn-1\n                    h=(h*20)^inp[j]\n                    d.add(h)\n                else:\n                    break  \n    print(len(d))"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 20189