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

Difficulty: interview

Starter code:

Solutions:
import sys
for _ in range(0,eval(input())):   
    d,inp,mp,n,q=set(),list(map(ord,list(sys.stdin.readline().strip()))),[x=='b' for x in list(sys.stdin.readline().strip())],eval(input()),ord('a')
    inps = [inp[i:] for i in range(len(inp))]
    inps.sort()
    op,prev= 0,''
    for ip in inps:
        	i,ct=0,0
        	while i < min(len(ip),len(prev)):
        		if prev[i] != ip[i]:
        			break
        		if mp[ip[i]-q]:
        			ct = ct+  1
        		i = i+1
        	while i < len(ip):
        		if mp[ip[i]-q]:
        			ct = ct + 1
        		if ct > n:
        			break
        		op,i= op+1,i+1
        	prev = ip
    print(op)

import sys
for _ in range(0,eval(input())):   
    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')
    for i in range(0,len(inp)):
        nn,h=n,0
        for j in range(i,len(inp)):
                if ( (mp[inp[j]-q]) or  nn>0 ):
                    if(mp[inp[j]-q] == False ):                
                        nn=nn-1
                    h=(h*20)^inp[j]
                    d.add(h)
                else:
                    break  
    print(len(d))

import sys
for _ in range(0,eval(input())):   
    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')
    for i in range(0,len(inp)):
        nn,h=n,0
        for j in range(i,len(inp)):
                if ( (mp[inp[j]-q]) or  nn>0 ):
                    if(mp[inp[j]-q] == False ):                
                        nn=nn-1
                    h=(h*128)^inp[j]
                    d.add(h)
                else:
                    break  
    print(len(d))

import sys
for _ in range(0,eval(input())):   
    d,inp,mp,n,q=set(),list(map(ord,list(sys.stdin.readline().strip()))),sys.stdin.readline().strip(),eval(input()),ord('a')
    for i in range(0,len(inp)):
        nn,h=n,0
        for j in range(i,len(inp)):
                if ( (mp[inp[j]-q]=='g') or  nn>0 ):
                    if((mp[inp[j]-q]=='g') == False ):                
                        nn=nn-1
                    h=(h*128)^inp[j]
                    d.add(h)
                else:
                    break  
    print(len(d))

import sys
for _ in range(0,eval(input())):   
    d,inp,mp,n,q=[],list(map(ord,list(sys.stdin.readline().strip()))),sys.stdin.readline().strip(),eval(input()),ord('a')
    for i in range(0,len(inp)):
        nn,h=n,0
        for j in range(i,len(inp)):
                if ( (mp[inp[j]-q]=='g') or  nn>0 ):
                    if((mp[inp[j]-q]=='g') == False ):                
                        nn=nn-1
                    h=(h*128)^inp[j]
                    d.append(h)
                else:
                    break  
    print(len(set(d)))

import sys
for _ in range(0,eval(input())):   
    d,ctr,inp,mp,n,q=[0]*4000000,0,list(map(ord,list(sys.stdin.readline().strip()))),sys.stdin.readline().strip(),eval(input()),ord('a')
    for i in range(0,len(inp)):
        nn,h=n,0
        for j in range(i,len(inp)):
                if ( (mp[inp[j]-q]=='g') or  nn>0 ):
                    if((mp[inp[j]-q]=='g') == False ):                
                        nn=nn-1
                    h=(h*128)^inp[j]
                    d[ctr],ctr=h,ctr+1
                else:
                    break  
    d=d[0:ctr]
    print(len(set(d)))

import sys
for _ in range(0,eval(input())):   
    d,c,inp,mp,n,q=[],0,list(map(ord,list(sys.stdin.readline().strip()))),sys.stdin.readline().strip(),eval(input()),ord('a')
    for i in range(0,len(inp)):
        nn,h=n,0
        for j in range(i,len(inp)):
                if ( (mp[inp[j]-q]=='g') or  nn>0 ):
                    if((mp[inp[j]-q]=='g') == False ):                
                        nn=nn-1
                    h=(h*128)^inp[j]
                    d+=[h]
                else:
                    break  
    print(len(set(d)))
    
    

import sys
for _ in range(0,eval(input())):   
    d,c,inp,mp,n,q=[],0,list(map(ord,list(sys.stdin.readline().strip()))),sys.stdin.readline().strip(),eval(input()),ord('a')
    for i in range(0,len(inp)):
        nn,h=n,0
        for j in range(i,len(inp)):
                if ( (mp[inp[j]-q]=='g') or  nn>0 ):
                    if((mp[inp[j]-q]=='g') == False ):                
                        nn=nn-1
                    h=(h*256)^inp[j]
                    d+=[h]
                else:
                    break  
    print(len(set(d)))
            

import sys
for _ in range(0,eval(input())):   
    d,c,inp,mp,n=[],0,sys.stdin.readline().strip(),sys.stdin.readline().strip(),eval(input())
    for i in range(0,len(inp)):
        nn,h=n,0
        for j in range(i,len(inp)):
                if ( (mp[ord(inp[j])-ord('a')]=='g') or  nn>0 ):
                    if((mp[ord(inp[j])-ord('a')]=='g') == False ):                
                        nn=nn-1
                    h=(h*256)^ord(inp[j])
                    d+=[h]
                else:
                    break  
    print(len(set(d)))
            

for _ in range(0,eval(input())):   
    d,c,inp,mp,n=[],0,input(),input(),eval(input())
    for i in range(0,len(inp)):
        nn,h=n,0
        for j in range(i,len(inp)):
                if ( (mp[ord(inp[j])-ord('a')]=='g') or  nn>0 ):
                    if((mp[ord(inp[j])-ord('a')]=='g') == False ):                
                        nn=nn-1
                    h=(h*256)^ord(inp[j])
                    d+=[h]
                else:
                    break  
    print(len(set(d)))