#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
const int mx = 2e6 + 10;
int convert[300];
struct Trie_2
{
struct Node
{
int child[4];
vector<int> v;
void reset()
{
for(int i = 0; i<4; i++) child[i] = -1;
}
};
Node nodes[mx];
int sz;
int create_node()
{
nodes[++sz].reset();
return sz;
}
void add_string(vector<int> dir,int id)
{
int pos = 0;
reverse(all(dir));
for(int c : dir)
{
if(nodes[pos].child[c] == -1) nodes[pos].child[c] = create_node();
pos = nodes[pos].child[c];
nodes[pos].v.push_back(id);
}
}
int find_string(string s, int l, int r)
{
int pos = 0;
for(char k : s)
{
int c = convert[k];
if(nodes[pos].child[c] == -1) return 0;
pos = nodes[pos].child[c];
}
return upper_bound(all(nodes[pos].v),r) - lower_bound(all(nodes[pos].v),l);
}
};
Trie_2 suffix;
struct Trie_1
{
struct Node
{
int child[4];
int exist, l, r;
void reset()
{
for(int i = 0; i<4; i++) child[i] = -1;
exist = 0;
l = INT_MAX;
r = INT_MIN;
}
};
Node nodes[mx];
int sz;
int create_node()
{
nodes[++sz].reset();
return sz;
}
void add_string(string s)
{
int pos = 0;
for(char k : s)
{
int c = convert[k];
if(nodes[pos].child[c] == -1) nodes[pos].child[c] = create_node();
pos = nodes[pos].child[c];
}
nodes[pos].exist++;
}
vector<int> tmp;
int t;
void dfs(int pos = 0)
{
int cnt = nodes[pos].exist;
// cout<<t<<'\n';
while(cnt--)
{
t++;
nodes[pos].l = min(nodes[pos].l,t);
nodes[pos].r = max(nodes[pos].r,t);
suffix.add_string(tmp,t);
}
for(int c = 0;c<4;c++)
{
if(nodes[pos].child[c] != -1)
{
tmp.push_back(c);
dfs(nodes[pos].child[c]);
nodes[pos].l = min(nodes[pos].l,nodes[nodes[pos].child[c]].l);
nodes[pos].r = max(nodes[pos].r,nodes[nodes[pos].child[c]].r);
tmp.pop_back();
}
}
}
pair<int,int> find_string(string s)
{
int pos = 0;
for(char k : s)
{
int c = convert[k];
if(nodes[pos].child[c] == -1) return make_pair(0,0);
pos = nodes[pos].child[c];
}
return make_pair(nodes[pos].l,nodes[pos].r);
}
};
Trie_1 prefix;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
convert['A'] = 0;
convert['U'] = 1;
convert['G'] = 2;
convert['C'] = 3;
prefix.nodes[0].reset();
suffix.nodes[0].reset();
int n,q;
cin>>n>>q;
while(n--)
{
string s;
cin>>s;
prefix.add_string(s);
}
prefix.dfs();
while(q--)
{
string a,b;
cin>>a>>b;
pair<int,int> tmp = prefix.find_string(a);
cout<<suffix.find_string(b,tmp.first,tmp.second)<<'\n';
}
return 0;
}
