#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, q;
unordered_map<char, ll> mp;
string s, s2;
ll pre[2][100005];
pll a[100005];
pair<pll, pll> qu[400005];
ll ans[100005];
struct node {
ll sz, rid;
vector<ll> is;
node *v[4];
node () {
sz = 0;
rid = -1;
iloop(0, 4) v[i] = nullptr;
}
void add(string s, ll ci, ll cid) {
sz++;
if (ci == (ll)s.length()) {is.push_back(cid); return;}
if (v[mp[s[ci]]] == nullptr) v[mp[s[ci]]] = new node();
v[mp[s[ci]]]->add(s, ci+1, cid);
}
ll dfs(ll cp, bool ir) {
rid = cp;
for (auto it : is) {pre[ir][it] = cp; cp++;}
iloop(0, 4) if (v[i] != nullptr) cp = v[i]->dfs(cp, ir);
return cp;
}
pll find(string s, ll ci) {
if (ci == (ll)s.length()) return {rid, rid + sz - 1};
if (v[mp[s[ci]]] == nullptr) return {0, -1};
return v[mp[s[ci]]]->find(s, ci + 1);
}
} *root, *rroot;
ll fenw[100005];
void upd(ll X, ll V) {
X++;
for (; X <= n; X += (X&(-X))) fenw[X] += V;
}
ll query(ll X) {
X++;
ll cans = 0;
for (; X; X -= (X&(-X))) cans += fenw[X];
return cans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
mp = {{'A', 0}, {'C', 1}, {'G', 2}, {'U', 3}};
cin >> n >> q;
root = new node();
rroot = new node();
iloop(0, n) {
cin >> s;
root->add(s, 0, i);
reverse(s.begin(), s.end());
rroot->add(s, 0, i);
}
root->dfs(0, 0);
rroot->dfs(0, 1);
iloop(0, n) {
a[i] = {pre[0][i], pre[1][i]};
//cout << pre[0][i] << " " << pre[1][i] << "\n";
}
sort(a, a + n);
iloop(0, q) {
cin >> s >> s2;
reverse(s2.begin(), s2.end());
pair<pll, pll> tq = {root->find(s, 0), rroot->find(s2, 0)};
//cout << tq.first.first << "," << tq.first.second << "," << tq.second.first << "," << tq.second.second << endl;
qu[4*i] = {{tq.first.second, tq.second.second}, {1, i}};
qu[4*i + 1] = {{tq.first.first - 1, tq.second.second}, {-1, i}};
qu[4*i + 2] = {{tq.first.second, tq.second.first - 1}, {-1, i}};
qu[4*i + 3] = {{tq.first.first - 1, tq.second.first - 1}, {1, i}};
}
sort(qu, qu + 4*q);
ll cid = 0;
iloop(0, 4*q) {
//cout << qu[i].first.first << "," << qu[i].first.second << ":" << qu[i].second.first << "," << qu[i].second.second << endl;
while (cid <= qu[i].first.first) {upd(a[cid].second, 1); cid++;}
ans[qu[i].second.second] += qu[i].second.first * query(qu[i].first.second);
}
iloop(0, q) cout << ans[i] << "\n";
}
