#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int SIZEMAX = 2000005;
const int INF = 1000000005;
struct Node {
int mn, mx, nxt[4]; vector<int> lis;
Node() : mn(INF), mx(-INF) {
memset(nxt, 0, sizeof nxt); } };
struct Event {
int typ; pair<int, int> seg;
Event(int _typ, pair<int, int> _seg) :
typ(_typ), seg(_seg) {} };
string str[MAXN], rev[MAXN];
Node trie1[SIZEMAX], trie2[SIZEMAX];
vector<Event> evn[MAXN];
pair<int, int> sgx[MAXN], sgy[MAXN];
int bit[MAXN], ans[MAXN], psx[MAXN], psy[MAXN];
void insert(Node trie[], int &tot, int nd, int ps, string &str, int p) {
if (ps != str.length()) {
if (!trie[nd].nxt[str[ps]]) {
trie[nd].nxt[str[ps]] = ++tot; }
insert(trie, tot, trie[nd].nxt[str[ps]], ps + 1, str, p); }
else {
trie[nd].lis.push_back(p); } }
void dfs(Node trie[], int &tot, int nd, int pos[]) {
for (int x : trie[nd].lis) {
pos[x] = ++tot;
trie[nd].mn = min(trie[nd].mn, tot);
trie[nd].mx = max(trie[nd].mx, tot); }
for (int i = 0; i < 4; ++i) {
if (trie[nd].nxt[i] != 0) {
dfs(trie, tot, trie[nd].nxt[i], pos);
trie[nd].mn = min(trie[nd].mn, trie[trie[nd].nxt[i]].mn);
trie[nd].mx = max(trie[nd].mx, trie[trie[nd].nxt[i]].mx); } } }
int _mn, _mx;
void getMinMax(Node trie[], int nd, int ps, string &str) {
if (ps == str.length()) {
_mn = trie[nd].mn; _mx = trie[nd].mx; }
else {
if (!trie[nd].nxt[str[ps]]) {
_mn = INF; _mx = -INF; }
else {
getMinMax(trie, trie[nd].nxt[str[ps]], ps + 1, str); } } }
void changeString(string &str) {
for (char &ch : str) {
if (ch == 'A') { ch = 0; }
if (ch == 'C') { ch = 1; }
if (ch == 'G') { ch = 2; }
if (ch == 'U') { ch = 3; } } }
void update(int ps, int vl) {
for (; ps < MAXN; ps += (ps & -ps)) {
bit[ps] += vl; } }
int query(int ps, int vl = 0) {
for (; ps > 0; ps -= (ps & -ps)) {
vl += bit[ps]; }
return vl; }
int main(void) {
#ifdef HOME
freopen("sellrna.in", "r", stdin);
freopen("sellrna.out", "w", stdout);
#endif
int n, m; cin >> n >> m;
for (int i = 1, nr1 = 1, nr2 = 1; i <= n; ++i) {
cin >> str[i]; changeString(str[i]);
rev[i] = str[i]; reverse(rev[i].begin(), rev[i].end());
insert(trie1, nr1, 1, 0, str[i], i); insert(trie2, nr2, 1, 0, rev[i], i); }
int nr; nr = 0; dfs(trie1, nr, 1, psx); nr = 0; dfs(trie2, nr, 1, psy);
for (int i = 1; i <= n; ++i) {
evn[psx[i]].push_back(Event(0, make_pair(psy[i], psy[i]))); }
for (int i = 1; i <= m; ++i) {
string str1, str2; cin >> str1 >> str2;
changeString(str1); changeString(str2); reverse(str2.begin(), str2.end());
getMinMax(trie1, 1, 0, str1); sgx[i] = make_pair(_mn, _mx);
getMinMax(trie2, 1, 0, str2); sgy[i] = make_pair(_mn, _mx);
if (sgx[i].first != INF and sgy[i].first != INF) {
evn[sgx[i].first - 1].push_back(Event(-i, sgy[i]));
evn[sgx[i].second].push_back(Event(i, sgy[i])); } }
for (int i = 0; i <= n; ++i) {
for (auto &ev : evn[i]) {
if (ev.typ == 0) {
update(ev.seg.first, 1); }
else {
ans[abs(ev.typ)] += (query(ev.seg.second) - query(ev.seg.first - 1)) * (ev.typ < 0 ? -1 : 1); } } }
for (int i = 1; i <= m; ++i) {
cout << ans[i] << "\n"; }
return 0; }
