#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <cassert>
#include <algorithm>
#define rep(i,n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;
string convert(string s) {
string o = "";
for (char c : s) {
if (c == 'A') o += 'a';
else if (c == 'G') o += 'b';
else if (c == 'C') o += 'c';
else o += 'd';
}
return o;
}
string read() {
string s;
cin >> s;
return convert(s);
}
struct BIT {
vector<int> xs;
int n;
BIT(int n) : n(n) {
xs.resize(n+1);
}
void add(int i, int v) {
for (int x=i+1; x<=n; x+=x&-x) xs[x] += v;
}
int sum(int i) {
int s = 0;
for (int x=i+1; x>0; x-=x&-x) s += xs[x];
return s;
}
int sum(int l, int r) {
return sum(r) - sum(l-1);
}
};
struct UF {
vector<int> U, R;
UF(int N) : U(N), R(N, 1) {
rep(i, N) U[i] = i;
}
int find(int x) {
if (U[x] == x) return x;
return U[x] = find(U[x]);
}
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (R[x] < R[y]) swap(x, y);
U[y] = x;
R[x] += R[y];
}
};
// with uniq
vector<int> radixSort(int p, vector<int> all, vector<string> &src, UF &uf) {
vector<int> s[5] = {};
vector<int> ret;
for (int x : all) {
if (src[x].size() == p) ret.pb(x);
else s[src[x][p]-'a'].pb(x);
}
while (ret.size() > 1) {
uf.unite(ret.front(), ret.back());
ret.pop_back();
}
if (!ret.empty()) ret[0] = uf.find(ret[0]);
rep(k, 5) if (!s[k].empty()) {
vector<int> r = radixSort(p+1, s[k], src, uf);
ret.insert(ret.end(), all(r));
}
return ret;
}
int N, Q;
string S[100000];
string Qpre[100000], Qsuf[100000];
int posX[300000], posY[300000];
int ans[100000];
vector<int> ps[300000];
int XL[100000], XR[100000];
vector<int> Qbegin[300000], Qend[300000];
int main() {
cin >> N >> Q;
rep(i, N) S[i] = read();
rep(i, Q) Qpre[i] = read(), Qsuf[i] = read(), reverse(all(Qsuf[i]));
vector<string> xs, ys;
rep(i, N) { // 0 ~ N-1
xs.pb(S[i]);
string Srev(S[i]);
reverse(all(Srev));
ys.pb(Srev);
}
rep(i, Q) { // N+q*2 <-> N+q*2+1
xs.pb(Qpre[i]);
xs.pb(Qpre[i]+'e');
ys.pb(Qsuf[i]);
ys.pb(Qsuf[i]+'e');
}
vector<int> xsi, ysi;
UF uf_x(N+2*Q), uf_y(N+2*Q);
rep(i, N+2*Q) xsi.pb(i), ysi.pb(i);
xsi = radixSort(0, xsi, xs, uf_x);
ysi = radixSort(0, ysi, ys, uf_y);
rep(i, N+2*Q) posX[i] = posY[i] = -1;
rep(i, xsi.size()) posX[xsi[i]] = i;
rep(i, ysi.size()) posY[ysi[i]] = i;
rep(i, N+2*Q) {
if (posX[i] == -1) posX[i] = posX[uf_x.find(i)];
if (posY[i] == -1) posY[i] = posY[uf_y.find(i)];
}
BIT bit(xsi.size());
rep(i, N) ps[posY[i]].pb(posX[i]);
rep(i, Q) {
int xl = posX[N+i*2], xr = posX[N+i*2+1];
int yl = posY[N+i*2], yr = posY[N+i*2+1];
XL[i] = xl, XR[i] = xr;
Qbegin[yl].pb(i);
Qend[yr].pb(i);
}
rep(y, ysi.size()) {
for (int q : Qbegin[y]) ans[q] -= bit.sum(XL[q], XR[q]);
for (int x : ps[y]) bit.add(x, 1);
for (int q : Qend[y]) ans[q] += bit.sum(XL[q], XR[q]);
}
rep(i, Q) cout << ans[i] << "\n";
return 0;
}
