#include<bits/stdc++.h>
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int MX = 2e6+2e3;
array<int, 4> ch[2][MX]; int Nn[2];
int cnt[2][MX]; int lb[2][MX];
map<char, int> con;
void pre()
{
con['A'] = 0;
con['G'] = 1;
con['C'] = 2;
con['U'] = 3;
ch[0][0] = ch[1][0] = {-1, -1, -1, -1};
return;
}
int create(int k)
{
Nn[k]++;
ch[k][Nn[k]] = {-1, -1, -1, -1};
return Nn[k];
}
void add(const string &s, int k, int LABEL)
{
int u = 0;
for(auto c: s)
{
if(ch[k][u][con[c]] == -1)
ch[k][u][con[c]] = create(k);
u = ch[k][u][con[c]];
}
cnt[k][u]++;
lb[k][u] = LABEL;
return;
}
int tin[2][MX];
int tout[2][MX];
vector<in> flt[2]; //flt[0] = ft[1] = {0};
void dfs(int u, int k)
{
tin[k][u] = flt[k].size();
if(cnt[k][u])
flt[k].pb({lb[k][u], cnt[k][u]});
for(int v: ch[k][u])
{
if(v == -1)
continue;
dfs(v, k);
}
tout[k][u] = flt[k].size();
return;
}
in help(const string &s, int k)
{
int u = 0;
for(auto c: s)
{
if(ch[k][u][con[c]] == -1)
return {1, 0};
u = ch[k][u][con[c]];
}
return {tin[k][u], tout[k][u]-1};
}
struct ps_tree
{
int tree[MX];
int left[MX];
int right[MX];
int N;
void build(int id, int l, int r)
{
int m = (l+r)/2;
if(l == r)
return;
left[id] = N++;
right[id] = N++;
build(left[id], l, m);
build(right[id], m+1, r);
return;
}
int init(int M)
{
N = 1;
build(1, 0, M);
return N++;
}
int copy(int u)
{
int x = N++;
tree[x] = tree[u];
left[x] = left[u];
right[x] = right[u];
return x;
}
int upd(int p, int val, int id, int l, int r)
{
int id_new = copy(id);
if(l == r)
{
tree[id_new]+=val;
return id_new;
}
int m = (l+r)/2;
if(p <= m)
left[id_new] = upd(p, val, left[id], l, m);
else
right[id_new] = upd(p, val, right[id], m+1, r);
tree[id_new] = tree[left[id_new]] + tree[right[id_new]];
return id_new;
}
int Query(int ql, int qr, int id, int l, int r)
{
if(qr < l || r < ql)
return 0;
if(ql <= l && r <= qr)
return tree[id];
int m = (l+r)/2;
int s1 = Query(ql, qr, left[id], l, m);
int s2 = Query(ql, qr, right[id], m+1, r);
return s1+s2;
}
};
signed main()
{
fast(); pre();
//cout << "hey" << endl;
int n, q; cin >> n >> q;
string s;
for(int i = 1; i <= n; i++)
{
cin >> s;
add(s, 0, i);
reverse(s.begin(), s.end());
add(s, 1, i);
}
flt[0] = flt[1] = {{0,0}};
dfs(0, 0); dfs(0, 1);
//cout << "hey" << endl;
int N = flt[0].size()-1;
vector<int> pres(n+1);
vector<int> VAL(N+1);
for(int i = 1; i <= N; i++)
{
auto [lbl, cnt] = flt[0][i];
pres[lbl] = i;
VAL[i] = cnt;
}
//cout << "hey" << endl;
vector<int> w(N+1);//where to change.
for(int i = 1; i <= N; i++)
{
flt[1][i][0] = pres[flt[1][i][0]];
w[flt[1][i][0]] = i;
}
//cout << "hi" << endl;
ps_tree work;
int root[N+1];
root[0] = work.init(N);
for(int i = 1; i <= N; i++)
root[i] = work.upd(w[i], VAL[i], root[i-1], 0, N);
//cout << "hey" << endl;
array<in, 2> Q;
for(int i = 0; i < q; i++)
{
string x, y; cin >> x >> y;
reverse(y.begin(), y.end());
Q = {help(x, 0), help(y, 1)};
if((Q[0][0] > Q[0][1]) || (Q[1][0] > Q[1][1]))
{
cout << "0\n";
continue;
}
//cout << Q[0][0] << " " << Q[0][1] << " " << Q[1][0] << " " << Q[1][1] << endl;
int ans = work.Query(Q[1][0], Q[1][1], root[Q[0][1]], 0, N) - work.Query(Q[1][0], Q[1][1], root[Q[0][0]-1], 0, N);
cout << ans << "\n";
}
/*for(int i = 1; i <= N; i++)
cout << VAL[i] << " ";
cout << endl;
for(int i = 1; i <= N; i++)
cout << w[i] << " ";
cout << endl;*/
return 0;
}
