#include<bits/stdc++.h>
#define name "TASK"
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 100010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
//#define int long long
#define inf 1000000000
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
using namespace std;
int convert(char t)
{
if(t == 'A') return 0;
if(t == 'U') return 1;
if(t == 'G') return 2;
if(t == 'C') return 3;
}
namespace Trie
{
struct node
{
node *child[4];
pii range;
node()
{
memset(child,0,sizeof child);
range = {-1,-1};
}
};
node *root = new node();
void add(string s,int id)
{
node *p = root;
for(char c : s)
{
if(p -> child[convert(c)] == NULL) p -> child[convert(c)] = new node();
p = p -> child[convert(c)];
if(p -> range.fi == -1) p -> range = {id,id};
else p -> range.se = id;
}
}
pii get(string s)
{
node *p = root;
for(char c : s)
{
if(p -> child[convert(c)] == NULL) return {-1,-1};
p = p -> child[convert(c)];
}
return p -> range;
}
}
namespace RevTrie
{
struct node
{
node *child[4];
vi save;
node()
{
memset(child,0,sizeof child);
}
};
node *root = new node();
void add(string s,int id)
{
node *p = root;
for(int i = s.size() - 1 ; i >= 0 ; i--)
{
if(p -> child[convert(s[i])] == NULL) p -> child[convert(s[i])] = new node();
p = p -> child[convert(s[i])];
p ->save.pb(id);
}
}
vi get(string s)
{
node *p = root;
vi v;
for(int i = s.size() - 1 ; i >= 0 ; i--)
{
if(p -> child[convert(s[i])] == NULL) return v;
p = p -> child[convert(s[i])];
}
return p -> save;
}
}
string s[maxn];
int n;
string p,q;
int t;
main()
{
if(fopen(name".inp","r"))
{
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> t;
fo(i,1,n) cin >> s[i];
sort(s + 1,s+ n + 1);
fo(i,1,n)
{
Trie::add(s[i],i);
RevTrie::add(s[i],i);
}
while(t--)
{
cin >> p >> q;
pii range = Trie::get(p);
vi v = RevTrie::get(q);
if(v.size() == 0 or range.fi == -1) cout << 0 << "\n";
else
{
int lb = lower_bound(v.begin(),v.end(),range.fi) - v.begin();
int ub = upper_bound(v.begin(),v.end(),range.se) - v.begin() - 1;
cout << (ub - lb + 1) << "\n";
}
}
}
