#include <bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N=1e5+5;
string s[N];
int valchild[255];
struct trie
{
trie *child[4];
int l,r,cn;
trie()
{
for(int i=0;i<4;i++) child[i]=NULL;
l=N,r=-N,cn=0;
}
} *root;
void ins(string &s,int idx)
{
trie *p=root;
for(int i=0;i<(int)s.size();i++)
{
int c=valchild[(int)s[i]];
if(p->child[c]==NULL) p->child[c]=new trie();
p=p->child[c];
p->l=min(p->l,idx);
p->r=max(p->r,idx);
}
p->cn++;
}
string tempdfs="";
int idxdfs=0;
void dfs(trie *p)
{
for(int i=0;i<(int)p->cn;i++) s[++idxdfs]=tempdfs;
for(int i=0;i<4;i++) if(p->child[i]!=NULL)
{
if(i==0) tempdfs.push_back('A');
else if(i==1) tempdfs.push_back('C');
else if(i==2) tempdfs.push_back('G');
else tempdfs.push_back('U');
dfs(p->child[i]);
tempdfs.pop_back();
}
delete p;
}
pair<int,int> get(string &s)
{
trie *p=root;
for(int i=0;i<(int)s.size();i++)
{
int c=valchild[(int)s[i]];
if(p->child[c]==NULL) return {-1,-1};
p=p->child[c];
}
return {p->l,p->r};
}
struct trie2
{
trie2 *child[4];
vector<int> v;
trie2()
{
for(int i=0;i<4;i++) child[i]=NULL;
v.clear();
}
} *root2;
void ins2(string &s,int idx)
{
trie2 *p=root2;
for(int i=0;i<(int)s.size();i++)
{
int c=valchild[(int)s[i]];
if(p->child[c]==NULL) p->child[c]=new trie2();
p=p->child[c];
p->v.push_back(idx);
}
}
int get2(pair<int,int> range,string &s)
{
trie2 *p=root2;
for(int i=0;i<(int)s.size();i++)
{
int c=valchild[(int)s[i]];
if(p->child[c]==NULL) return 0;
p=p->child[c];
}
int r=upper_bound(p->v.begin(),p->v.end(),range.se)-p->v.begin(),l=lower_bound(p->v.begin(),p->v.end(),range.fi)-p->v.begin();
return r-l;
}
void solve()
{
int n,q;
cin >> n >> q;
valchild['A']=0;valchild['C']=1;valchild['G']=2;valchild['U']=3;
root=new trie();
for(int i=1;i<=n;i++)
{
cin >> s[i];
ins(s[i],-1);
}
dfs(root);
root=new trie();
root2=new trie2();
for(int i=1;i<=n;i++)
{
ins(s[i],i);
reverse(s[i].begin(),s[i].end());
ins2(s[i],i);
}
while(q--)
{
string s,t;
cin >> s >> t;
reverse(t.begin(),t.end());
pair<int,int> range=get(s);
if(range.fi==range.se&&range.fi==-1) cout << 0 << endl;
else cout << get2(range,t) << endl;
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("hanhhhh.inp","r",stdin);
//freopen("hanhhhh.out","w",stdout);
int t=1;
//cin >> t;
while(t--) solve();
return 0;
}
