#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <algorithm>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const sigma = 4;
struct Trie{
std::vector<int> ids;
Trie* p[sigma];
Trie() {
for(int i = 0; i < sigma; i++)
p[i] = nullptr;
}
};
int const bigsigma = 256;
char mp[1 + bigsigma];
void _add(Trie* &root, std::string &s, int pos, int id) {
if(root == nullptr)
root = new Trie();
if(s.size() == pos)
root->ids.push_back(id);
else
_add(root->p[mp[s[pos]]], s, pos + 1, id);
}
void dfs(Trie* &root, int target, std::vector<int> &parc, std::vector<int> &start, std::vector<int> &stop) {
for(int h = 0; h < root->ids.size(); h++) {
int id = root->ids[h];
if(target < id)
start[id - 1 - target] = parc.size();
}
for(int h = 0; h < root->ids.size(); h++) {
int id = root->ids[h];
if(id <= target)
parc.push_back(id);
}
for(int h = 0; h < sigma; h++)
if(root->p[h] != nullptr)
dfs(root->p[h], target, parc, start, stop);
for(int h = 0; h < root->ids.size(); h++) {
int id = root->ids[h];
if(target < id)
stop[id - 1 - target] = parc.size() - 1;
}
}
Trie *root = nullptr, *root2 = nullptr;
class FenwickTree{
private:
int n;
std::vector<int> aib;
public:
FenwickTree(int n_) {
n = n_;
aib.resize(1 + n);
}
void update(int pos, int val) {
if(pos == 0) {
aib[0] += val;
return ;
}
for(int x = pos; x <= n; x += (x ^ (x & (x - 1))))
aib[x] += val;
}
int query(int pos) {
if(pos < 0)
return 0;
int result = 0;
for(int x = pos; 0 < x; x = (x & (x - 1)))
result += aib[x];
return result + aib[0];
}
};
int const nmax = 100000;
int sol[1 + nmax];
int main() {
mp['A'] = 0;
mp['G'] = 1;
mp['C'] = 2;
mp['U'] = 3;
int n, q;
std::cin >> n >> q;
for(int i = 1; i <= n; i++) {
std::string s;
std::cin >> s;
_add(root, s, 0, i);
std::reverse(s.begin(), s.end());
_add(root2, s, 0, i);
}
for(int i = 1;i <= q; i++) {
std::string p, q;
std::cin >> p >> q;
std::reverse(q.begin(), q.end());
_add(root, p, 0, n + i);
_add(root2, q, 0, n + i);
}
std::vector<int> parc1, start1(q), stop1(q);
std::vector<int> parc2, start2(q), stop2(q);
std::vector<int> pos1(n + 1);
dfs(root, n, parc1, start1, stop1);
dfs(root2, n, parc2, start2, stop2);
for(int i = 0; i < n; i++)
pos1[parc1[i]] = i;
std::vector<std::vector<std::pair<int,int>>> events(1 + n);
for(int i = 0; i < q; i++) {
if(start2[i] <= stop2[i]) {
events[stop2[i]].push_back({i, 1});
if(0 < start2[i])
events[start2[i] - 1].push_back({i, -1});
}
}
FenwickTree aib(1 + n);
for(int i = 0; i < n; i++) {
aib.update(pos1[parc2[i]], 1);
for(int h = 0; h < events[i].size(); h++) {
int id = events[i][h].first;
sol[id] += events[i][h].second * (aib.query(stop1[id]) - aib.query(start1[id] - 1));
}
}
for(int i = 0; i < q; i++)
std::cout << sol[i] << '\n';
return 0;
}
