/*
Solution:
����n����Ԫ�ַ�����
���Ƕ���ÿ�������Ԫ�ַ�����
�ж��ٸ�t1�滻�õ�t2�ķ�ʽ
ֱ�ӿ��Ǳ���
����t1������Щ���Ի���dfs�������������ٻ�Ϊֹ������t2�ͽ��� 
�����п��ܱ�ջ 
������ô��������
��ôֻ�ܻ�һ��
ֱ��ö�����
��ö�ٻ�Ϊ��һ��
check�����һ��һ�������� 
*/
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+7,M=1e6+7;
int n,q,ans=0,len;
string s1[N],s2[N];
string t1,t2;
bool check_same(string s)//�ж�s�Ƿ�=t2 
{
	if(s.size()!=t2.size()) return 0;
	for(int i=0;i<len;i++)
	    if(s[i]!=t2[i])
		   return 0;
    return 1;
}
string work(string s,int pos,int k)//��s�ӵ�posλ�����滻Ϊsk2 
{
	for(int i=pos;i<pos+s1[k].size();i++)
	{
		if(s[i]!=s1[k][i-pos])
		{
			string aa;
			aa[0]=' ';
			return aa;
		}
		s[i]=s2[k][i-pos];
	}
	return s;
}
int dfs(string s)//s�䵽t2�ķ����� 
{
	long long ans=0;
	for(int i=0;i<len;i++)//ö��x 
	{
	 	for(int j=1;j<=n;j++)//ö�����ĸ��仯 
 		{
		 	string s2=work(s,i,j);
		 	if(check_same(s2))
		 	{
		 		ans++;
		    }
	    }	
	}
	return ans;
}
signed main()
{
	freopen("replace.in","r",stdin);
	freopen("replace.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>s1[i]>>s2[i];
	}
	for(int i=1;i<=q;i++)
	{
		cin>>t1>>t2;
		len=t1.size();
		if(len!=t2.size())
		{
			cout<<0<<'\n';
			continue;
		}
		cout<<dfs(t1)<<'\n';
	}
	return 0;
}
/*
4 2
xabcx xadex
ab cd
bc de
aa bb
xabcx xadex
aaaa bbbb
*/
