#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5 + 5;
int n,m;
string s[N],p[N],q[N];
struct Trie {
struct Node {
Node *child[4];
int idx;
vector<int>vec;
Node(int _num) {
for (int i = 0; i < 4; i++) child[i] = NULL;
idx = _num;
vec.clear();
}
};
int cur,numNode;
Node *root;
Trie(): cur(0) {
numNode = 0;
root = new Node(numNode);
};
void add(string &s,int id) {
Node *p = root;
for (auto x: s) {
int c = 0;
if (x == 'A') c = 0;
else if (x == 'G') c = 1;
else if (x == 'C') c = 2;
else if (x == 'U') c = 3;
if (p -> child[c] == NULL) p -> child[c] = new Node(++numNode);
p = p -> child[c];
(p -> vec).push_back(id);
}
}
vector<int> get(string &s) {
Node *p = root;
for (auto x: s) {
int c = 0;
if (x == 'A') c = 0;
else if (x == 'G') c = 1;
else if (x == 'C') c = 2;
else if (x == 'U') c = 3;
if (p -> child[c] == NULL) {
vector<int>nullVec;
return nullVec;
}
p = p -> child[c];
}
return (p -> vec);
}
int getNum(string &s) {
Node *p = root;
for (auto x: s) {
int c = 0;
if (x == 'A') c = 0;
else if (x == 'G') c = 1;
else if (x == 'C') c = 2;
else if (x == 'U') c = 3;
if (p -> child[c] == NULL) return 0;
p = p -> child[c];
}
return (p -> vec).size();
}
int getIdx(string &s) {
Node *p = root;
for (auto x: s) {
int c = 0;
if (x == 'A') c = 0;
else if (x == 'G') c = 1;
else if (x == 'C') c = 2;
else if (x == 'U') c = 3;
if (p -> child[c] == NULL) return 0;
p = p -> child[c];
}
return (p -> idx);
}
vector<int>tin,tout;
int timeDFS;
void dfs(Node *u) {
tin[u -> idx] = ++timeDFS;
for (int i = 0; i < 4; i++)
if (u -> child[i] != NULL) dfs(u -> child[i]);
tout[u -> idx] = timeDFS;
}
void build() {
tin.assign(numNode + 2,0);
tout.assign(numNode + 2,0);
timeDFS = 0;
Node *p = root;
dfs(p);
}
};
namespace sub2 {
Trie pre,suf;
int vis[5005];
void solve() {
for (int i = 1; i <= n; i++) {
pre.add(s[i],i);
reverse(s[i].begin(),s[i].end());
suf.add(s[i],i);
reverse(s[i].begin(),s[i].end());
}
for (int i = 1; i <= m; i++) {
vector<int>tmp1 = pre.get(p[i]);
vector<int>tmp2 = suf.get(q[i]);
for (auto x: tmp1) vis[x] = 1;
int ans = 0;
for (auto x: tmp2)
if (vis[x]) ans++;
cout << ans << "\n";
for (auto x: tmp1) vis[x] = 0;
}
}
}
namespace sub3 {
Trie suf,T[350];
map<string,int>mp;
bool check_condition() {
int sumS = 0,sumP = 0,sumQ = 0;
for (int i = 1; i <= n; i++) sumS += s[i].size();
for (int i = 1; i <= m; i++) {
sumP += p[i].size();
sumQ += q[i].size();
}
return (sumS <= 1e5 && sumP <= 1e5 && sumQ <= 1e5);
}
void solve() {
for (int i = 1; i <= n; i++) {
reverse(s[i].begin(),s[i].end());
suf.add(s[i],i);
reverse(s[i].begin(),s[i].end());
}
int num = 0;
for (int i = 1; i <= m; i++) {
if (mp.find(q[i]) != mp.end()) continue;
mp[q[i]] = ++num;
vector<int>tmp = suf.get(q[i]);
for (auto x: tmp) T[num].add(s[x],x);
}
for (int i = 1; i <= m; i++) {
int id = mp[q[i]];
cout << T[id].getNum(p[i]) << "\n";
}
}
}
namespace sub4 {
Trie pre,suf;
const int maxN = 3e6 + 5;
int ans[N],bit[maxN];
struct Data {
int l,r,type,x,idx;
};
vector<Data>vec;
vector<pii>points;
void update(int i,int x) {
for (; i < maxN; i += i & (-i)) bit[i] += x;
}
int get(int i) {
int ans = 0;
for (; i > 0; i -= i & (-i)) ans += bit[i];
return ans;
}
void solve() {
for (int i = 1; i <= n; i++) {
pre.add(s[i],i);
reverse(s[i].begin(),s[i].end());
suf.add(s[i],i);
reverse(s[i].begin(),s[i].end());
}
for (int i = 1; i <= m; i++) {
pre.add(p[i],i);
suf.add(q[i],i);
}
pre.build();
suf.build();
for (int i = 1; i <= n; i++) {
int x = pre.getIdx(s[i]);
reverse(s[i].begin(),s[i].end());
int y = suf.getIdx(s[i]);
reverse(s[i].begin(),s[i].end());
x = pre.tin[x],y = suf.tin[y];
points.push_back({y,x});
}
for (int i = 1; i <= m; i++) {
int x = pre.getIdx(p[i]);
int y = suf.getIdx(q[i]);
vec.push_back({pre.tin[x],pre.tout[x],-1,suf.tin[y] - 1,i});
vec.push_back({pre.tin[x],pre.tout[x],1,suf.tout[y],i});
}
sort(vec.begin(),vec.end(),[&](Data &a,Data &b) {
return a.x < b.x;
});
sort(points.begin(),points.end());
int j = 0;
for (int i = 0; i < (int)vec.size(); i++) {
while (j < (int)points.size() && points[j].fi <= vec[i].x) {
update(points[j].se,1);
j++;
}
ans[vec[i].idx] += vec[i].type * (get(vec[i].r) - get(vec[i].l - 1));
}
for (int i = 1; i <= m; i++) cout << ans[i] << "\n";
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> s[i];
for (int i = 1; i <= m; i++) {
cin >> p[i] >> q[i];
reverse(q[i].begin(),q[i].end());
}
//if (n <= 5000 && m <= 5000) sub2::solve();
//else if (sub3::check_condition()) sub3::solve();
//else
sub4::solve();
}
