#include <bits/stdc++.h>
using namespace std;
#define bit(n,i) ((n>>i)&1)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define ep emplace_back
#define pii pair<int,int>
#define piii pair<int,pii>
#define fi first
#define se second
#define ll long long
const int MOD=1e9+7;
const int base=31;
const int N=1e5+5;
int n,q;
string v[N];
int val(char c)
{
if (c=='A') return 0;
if (c=='G') return 1;
if (c=='C') return 2;
return 3;
}
struct Trie
{
int l,r;
Trie *child[4];
Trie()
{
l=1e9,r=-1e9;
memset(child,0,sizeof child);
}
};
Trie root;
void trieAdd(const string &s,int pos)
{
Trie *p=&root;
int n=s.size();
for (int i=0;i<n;i++)
{
int c=val(s[i]);
if (!p->child[c]) p->child[c]=new Trie();
p=p->child[c];
p->l=min(p->l,pos);
p->r=max(p->r,pos);
}
}
pair<int,int>getRange(const string &s)
{
Trie *p=&root;
int n=s.size();
for (int i=0;i<n;i++)
{
int c=val(s[i]);
if (!p->child[c]) return {0,0};
p=p->child[c];
}
return {p->l,p->r};
}
struct revTrie
{
revTrie *child[4];
vector<int>vi;
revTrie()
{
vi.clear();
memset(child,0,sizeof child);
}
};
revTrie r;
void revAdd(const string &s,int pos)
{
revTrie *p=&r;
int n=s.size();
for (int i=n-1;~i;i--)
{
int c=val(s[i]);
if (!p->child[c]) p->child[c]=new revTrie();
p=p->child[c];
p->vi.pb(pos);
}
}
int revFind(const string &s,pair<int,int>range)
{
revTrie *p=&r;
int n=s.size();
for (int i=n-1;~i;i--)
{
int c=val(s[i]);
p=p->child[c];
}
int it1=lower_bound(all(p->vi),range.fi)-(p->vi.begin());
int it2=upper_bound(all(p->vi),range.se)-(p->vi.begin());
return it2-it1;
}
int main()
{
#ifdef Hyojin
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif //Hyojin
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>q;
for (int i=1;i<=n;i++)
{
cin>>v[i];
}
sort(v+1,v+n+1);
for (int i=1;i<=n;i++)
{
trieAdd(v[i],i);
}
for (int i=1;i<=n;i++)
{
revAdd(v[i],i);
}
while (q--)
{
string p,q;
cin>>p>>q;
pair<int,int>x=getRange(p);
if (x.se==0) cout<<0;
else
{
int ans=revFind(q,x);
cout<<ans;
}
cout<<"\n";
}
return 0;
}
