#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ld double
#define FOR(i,l,r) for(ll i = (l), _r = (r); i <= _r; i++)
#define FORNG(i,r,l) for(ll i = (r), _l = (l); i >= _l; i--)
#define REP(i,r) for(ll i = 0, _r = (r); i <= _r; i++)
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define size(v) ((ll)(v).size())
#define all(v) (v).begin(),(v).end()
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
const ll MOD = 1e9 + 7, N = 1e5 + 10, INF = 1e9, LOG = 21;
const ll MAXNODE = 4e6 + 10, W = 26;
struct Node{
Node *child[W];
vector<ll> vec;
Node(){
memset(child, 0, sizeof child);
}
}T[MAXNODE];
ll cntUsedNode = 0;
Node *NEW(){return &T[++cntUsedNode];}
struct TRIE{
Node *root = NEW();
void addStr(string &s,ll idx){
Node *p = root;
for(char c : s){
if(!p->child[c - 'A'])p->child[c - 'A'] = NEW();
p = p->child[c - 'A'];
p->vec.pb(idx);
}
}
pair<ll,ll> getRange(string &prefix){
Node *p = root;
for(char c : prefix){
if(!p->child[c - 'A'])return {-1, -1};
p = p->child[c - 'A'];
}
return {p->vec.front(), p->vec.back()};
}
ll query(string &sufix,ll l,ll r){
Node *p = root;
for(char c : sufix){
if(!p->child[c - 'A'])return 0;
p = p->child[c - 'A'];
}
return upper_bound(all(p->vec), r) - lower_bound(all(p->vec), l);
}
}Trie,revTrie;
ll n,q;
string s[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>q;
FOR(i,1,n)cin>>s[i];
sort(s + 1, s + 1 + n);
FOR(i,1,n){
Trie.addStr(s[i], i);
reverse(all(s[i]));
revTrie.addStr(s[i], i);
}
while(q--){
string p,q;cin>>p>>q;
auto [l, r] = Trie.getRange(p);
if(l == -1){
cout<<0<<endl;
continue;
}
reverse(all(q));
cout<<revTrie.query(q, l, r)<<endl;
}
}
