// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const int MOD = 998244353, INF = 1e9 + 7;
//fen
struct Fen
{
int n;
vector<int> bit;
void init(int len){
n = len;
bit.assign(n + 1, 0);
}
void upd(int pos, int val){
for(; pos<=n; pos += pos & -pos) bit[pos] += val;
}
int qr(int pos){
int ans = 0;
for(; pos>0; pos -= pos & -pos) ans += bit[pos];
return ans;
}
};
//var
const int maxn = 2e6 + 10;
int n, q;
string inp[maxn];
int tin1[maxn], tin2[maxn], tout1[maxn], tout2[maxn];
Fen ft;
int eul1 = 0, eul2 = 0;
//trie
struct node
{
int cnt;
array<int, 4> child;
node(){
cnt = 0;
child.fill(-1);
}
};
vector<node> tree1(2);
vector<node> tree2(2); //rev
int id1 = 1, id2 = 1;
int new_node1(){
id1++;
if(id1 >= tree1.size()) tree1.push_back(node());
return id1;
}
int new_node2(){
id2++;
if(id2 >= tree2.size()) tree2.push_back(node());
return id2;
}
void add(string a){
int pos1 = 1;
for(int i=0; i<a.size(); ++i){
int x = a[i];
if(tree1[pos1].child[x - '0'] == -1){
tree1[pos1].child[x - '0'] = new_node1();
}
pos1 = tree1[pos1].child[x - '0'];
}
tree1[pos1].cnt++;
int pos2 = 1;
for(int i = a.size() - 1; i>=0; --i){
int x = a[i];
if(tree2[pos2].child[x - '0'] == -1){
tree2[pos2].child[x - '0'] = new_node2();
}
pos2 = tree2[pos2].child[x - '0'];
}
tree2[pos2].cnt++;
}
pair<int, int> address(string a){
int pos1 = 1;
for(int i=0; i<a.size(); ++i){
int x = a[i];
pos1 = tree1[pos1].child[x - '0'];
}
int pos2 = 1;
for(int i = a.size() - 1; i>=0; --i){
int x = a[i];
pos2 = tree2[pos2].child[x - '0'];
}
return make_pair(tin1[pos1], tin2[pos2]);
}
void dfs1(int a){
tin1[a] = ++eul1;
for(int i=0; i<4; ++i){
if(tree1[a].child[i] != -1) dfs1(tree1[a].child[i]);
}
tout1[a] = eul1;
}
void dfs2(int a){
tin2[a] = ++eul2;
for(int i=0; i<4; ++i){
if(tree2[a].child[i] != -1) dfs2(tree2[a].child[i]);
}
tout2[a] = eul2;
}
string trans(string a){
string nxt = "";
for(int j=0; j<a.size(); ++j){
if(a[j] == 'A') nxt += '0';
else if(a[j] == 'U') nxt += '1';
else if(a[j] == 'G') nxt += '2';
else if(a[j] == 'C') nxt += '3';
}
return nxt;
}
//
int cntoqr = 0;
vector<int> upda[maxn]; // y that have to upd with x = i
vector<pair<int, int>> oqr[maxn]; // {y, id} for qr have x = i
int anoqr[maxn]; // ans for ofqr i
//anoqr[bb] - anoqr[ba] - anoqr[ab] + anoqr[aa]
struct queries
{
int ab, ba, aa, bb;
queries(){
ab = ba = aa = bb = -INF;
}
void init(int x1, int x2, int y1, int y2){
bb = ++cntoqr;
ab = ++cntoqr;
ba = ++cntoqr;
aa = ++cntoqr;
oqr[x2].push_back({y2, bb});
oqr[x1 - 1].push_back({y2, ab});
oqr[x2].push_back({y1 - 1, ba});
oqr[x1 - 1].push_back({y1 - 1, aa});
}
};
vector<queries> qrs;
void ope(string p, string q){
int pos1 = 1;
for(int i=0; i<p.size(); ++i){
int x = p[i];
if(tree1[pos1].child[x - '0'] == -1){
qrs.push_back(queries());
return;
}
pos1 = tree1[pos1].child[x - '0'];
}
int pos2 = 1;
for(int i = q.size() - 1; i>=0; --i){
int x = q[i];
if(tree2[pos2].child[x - '0'] == -1){
qrs.push_back(queries());
return;
}
pos2 = tree2[pos2].child[x - '0'];
}
queries cc;
cc.init(tin1[pos1], tout1[pos1], tin2[pos2], tout2[pos2]);
qrs.push_back(cc);
}
void solve(){
cin >> n >> q;
for(int i=1; i<=n; ++i){
cin >> inp[i];
inp[i] = trans(inp[i]);
add(inp[i]);
}
dfs1(1);
dfs2(1);
ft.init(eul2);
for(int i=1; i<=n; ++i){
pair<int, int> x = address(inp[i]);
upda[x.fi].push_back(x.se);
}
while(q--){
string p, q;cin >> p >> q;
ope(trans(p), trans(q));
}
for(int i=1; i<=eul1; ++i){
for(auto &elm: upda[i]) ft.upd(elm, 1);
for(auto &elm: oqr[i]){
anoqr[elm.se] = ft.qr(elm.fi);
}
}
for(auto &elm: qrs){
if(elm.bb == -INF){
cout << 0 << '\n';
}
else{
int ans = anoqr[elm.bb] - anoqr[elm.ba] - anoqr[elm.ab] + anoqr[elm.aa];
cout << ans << '\n';
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
