#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
using namespace std;
ll powmod(ll base,ll exponent,ll mod){
ll ans=1;
if(base<0) base+=mod;
while(exponent){
if(exponent&1)ans=(ans*base)%mod;
base=(base*base)%mod;
exponent/=2;
}
return ans;
}
ll gcd(ll a, ll b){
if(b==0) return a;
else return gcd(b,a%b);
}
const int INF = 2e9;
const ll INFLL = 4e18;
const int upperlimit = 1e6+1;
const int mod = 1e9+7;
const int letters = 4;
string inp[upperlimit];
int toint(char c){
if(c=='A') return 0;
if(c=='U') return 1;
if(c=='G') return 2;
return 3;
}
struct trie_node
{
vi indices;
int child[letters];
trie_node(){
for(int i = 0; i < letters; i++) child[i]=0;
}
};
trie_node default_trienode;
class trie {
vector<trie_node> tree;
int cur_node,sz=1;
public:
trie() {
tree.resize(1);
}
void addstring(string s,int ind){
cur_node=0;
for(auto i : s){
tree[cur_node].indices.pb(ind);
if(! tree[cur_node].child[toint(i)]){
tree[cur_node].child[toint(i)]=sz++;
tree.pb(default_trienode);
}
cur_node = tree[cur_node].child[toint(i)];
}
tree[cur_node].indices.pb(ind);
}
pii query_range(string s){
cur_node = 0;
for(auto i : s){
if(! tree[cur_node].child[toint(i)]) return(mp(0,0));
cur_node = tree[cur_node].child[toint(i)];
}
return mp(tree[cur_node].indices.front(),tree[cur_node].indices.back());
}
int query(string s,int l,int r){
cur_node = 0;
for(auto i : s){
if(! tree[cur_node].child[toint(i)]) return 0;
cur_node = tree[cur_node].child[toint(i)];
}
return int(upper_bound(tree[cur_node].indices.begin(),tree[cur_node].indices.end(),r) - lower_bound(tree[cur_node].indices.begin(),tree[cur_node].indices.end(),l));
}
};
int main(){
int n,m;
string pref,suff;
trie str,revstr;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> inp[i];
sort(inp+1,inp+n+1);
for(int i = 1; i <= n; i++){
str.addstring(inp[i],i);
reverse(inp[i].begin(),inp[i].end());
revstr.addstring(inp[i],i);
}
while(m--){
cin >> pref >> suff;
pii range = str.query_range(pref);
reverse(suff.begin(),suff.end());
cout << revstr.query(suff,range.F,range.S) << "\n";
}
return 0;
}
