#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pi3 = pair<pii, int>;
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F first
#define S second
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define pb push_back
#define minr(a, b) a = min(a, b);
#define maxr(a, b) a = max(a, b);
#define shit cout << "shit\n" << flush;
#define tl while(1&1) continue;
#define rand(l, r) uniform_int_distribution<int64_t>(l,r)(rng)
random_device device; default_random_engine rng(device());
const int Mod = 1e9 + 7; //998244353;
const int LG = 64;
const int SQ = 500;
const int Inf = 2e9 + 10;
const int maxA = 5;
const int maxN = 1e5 + 10;
int n, m;
int NewIdx[26];
string s[maxN];
struct Node {
int l, r;
vector <int> st;
Node *child[maxA];
Node() {
child[0] = child[1] = child[2] = child[3] = child[4] = nullptr;
l = r = 0;
}
void extend(int idx) {
if(child[idx] == nullptr)
child[idx] = new Node();
}
void add(int i, int idx) {
st.pb(idx);
if(l == 0)
l = idx;
r = idx;
if(i >= sz(s[idx]))
return;
int x = NewIdx[s[idx][i]-'A'];
extend(x);
child[x]->add(i+1, idx);
}
pair <Node*, bool> get(string &t, int idx) {
if(idx >= sz(t)) {
return make_pair(this, true);
}
int x = NewIdx[t[idx]-'A'];
if(child[x] == nullptr)
return make_pair(this, false);
return child[x]->get(t, idx+1);
}
};
Node *r = new Node();
Node *rv = new Node();
int main() {
IOS;
NewIdx['A'-'A'] = 0;
NewIdx['C'-'A'] = 1;
NewIdx['G'-'A'] = 2;
NewIdx['U'-'A'] = 3;
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> s[i];
sort(s, s+n+1);
for(int i = 1; i <= n; i++) {
r->add(0, i);
reverse(all(s[i]));
rv->add(0, i);
}
while(m--) {
string p, q;
cin >> p >> q;
reverse(all(q));
pair<Node*, bool> x = r->get(p, 0);
pair<Node*, bool> y = rv->get(q, 0);
if(!(x.S & y.S)) {
cout << 0 << "\n";
continue;
}
int L = lower_bound(all((y.F)->st), (x.F)->l) - (y.F)->st.begin();
int R = upper_bound(all((y.F)->st), (x.F)->r) - (y.F)->st.begin();
cout << R-L << "\n";
}
}
