#include <bits/stdc++.h>
#define ll int
#define INF (ll)1e9+1
#define bit(mask, id) ((mask >> id) & 1LL)
#define pb push_back
#define el '\n'
#define ft first
#define sc second
#define ii pair<ll,ll>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FORD(i, l, r) for(int i = (l); i >= (r); --i)
#define str string
#define all(a,i) memset(a,i,sizeof(a))
#define al(a) a.begin(),a.end()
/////////////////////////////
const long long oo = 1e18;
const int N = 5e5 + 9;
using namespace std;
struct TRIE{
struct Node{
ll l,r;
vector<ll>exist;
ll child[26];
};
Node node[N];
ll curnode;
ll new_node()
{
++curnode;
node[curnode].l = INF;
node[curnode].r = 0;
all(node[curnode].child,-1);
node[curnode].exist.clear();
return curnode;
}
TRIE(){
curnode = -1;
new_node();
}
void add(str s, ll id)
{
ll pos = 0;
for(auto x:s)
{
ll c = x-'A';
if(node[pos].child[c]==-1)
{
node[pos].child[c] = new_node();
}
pos = node[pos].child[c];
node[pos].l = min(node[pos].l,id);
node[pos].r = max(node[pos].r,id);
//cout<<pos<<' '<<node[pos].l<<' '<<node[pos].r<<el;
node[pos].exist.pb(id);
}
}
bool fi(str s)
{
ll pos = 0;
for(auto x:s)
{
ll c = x-'A';
if(node[pos].child[c]==-1) return 0;
pos = node[pos].child[c];
}
return 1;
}
vector<ll>suffix(str s)
{
vector<ll>ans;
if(!fi(s)) return ans;
ll pos = 0;
for(auto x:s)
{
ll c = x-'A';
pos = node[pos].child[c];
}
return node[pos].exist;
}
ii prefix(str s)
{
if(!fi(s)) return {0,0};
ll pos = 0;
for(auto x:s)
{
ll c = x-'A';
pos = node[pos].child[c];
}
return {node[pos].l, node[pos].r};
}
};
TRIE pre, suf;
str a[N];
ll n,Q;
ll Count(vector<ll>&v, ll l, ll r)
{
if(v.empty()) return 0;
ll L = lower_bound(al(v),l)-v.begin();
ll R = upper_bound(al(v),r)-v.begin();
//cout<<L<<' '<<R<<el;
return R-L;
}
signed main()
{
#define TASK "rna"
if(fopen(TASK ".inp","r")) {
freopen (TASK ".inp","r",stdin);
freopen (TASK ".out","w",stdout);
//freopen (TASK ".ans","w",stdout);
}
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
cin>>n>>Q;
FOR(i,1,n) cin>>a[i];
sort(a+1,a+1+n);
// FOR(i,1,n) cout<<a[i]<<el;
FOR(i,1,n)
{
pre.add(a[i],i);
str t = a[i];
reverse(al(t));
suf.add(t,i);
//cout<<a[i]<<' '<<t<<el;
}
FOR(i,1,Q)
{
str p,q; cin>>p>>q;
// cout<<p<<' '<<q<<el;
reverse(al(q));
auto [l,r] = pre.prefix(p);
vector<ll>ans = suf.suffix(q);
// cout<<l<<' '<<r<<el;
// for(auto x:ans) cout<<x<<' ';
// cout<<el;
//ans.pb(INF);
cout<<Count(ans,l,r)<<el;
}
return 0;
}
