#include <bits/stdc++.h>
using namespace std;
#define TASK "long"
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define GETBIT(mask, i) ((mask) >> (i) & 1)
#define MASK(i) ((1LL) << (i))
#define SZ(x) ((int)(x).size())
#define mp make_pair
#define CNTBIT(mask) __builtin_popcount(mask)
template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;};
template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;};
typedef pair<int, int> ii;
const int N = 2e6 + 5;
const int inf = 1e9 + 7;
const long long INF = (long long)1e18 + 7;
const int mod = 1e9 + 7;
void add(int &x, int y) {x += y; if (x >= mod) x -= mod;}
void sub(int &x, int y) {x -= y; if (x < 0) x += mod;}
int mul(int x, int y) {return 1LL * x * y % mod;}
// -----------------------------------------//
int id(char c) {
if (c == 'A') return 0;
if (c == 'C') return 1;
if (c == 'G') return 2;
return 3;
}
int t1[4 * N][4], t2[4 * N][4];
pair<int, int> pos1[4 * N];
int n, q;
string a[N];
int timer1 = 0;
void add1(string s, int idx) {
int root = 0;
for(char c: s) {
int i = id(c);
if (t1[root][i] == 0) {
t1[root][i] = ++timer1;
pos1[timer1] = {inf, -inf};
}
root = t1[root][i];
minimize(pos1[root].fi, idx);
maximize(pos1[root].se, idx);
}
}
pair<int, int> query1(string s) {
int root = 0;
for(char c: s) {
int i = id(c);
if (t1[root][i] == 0) return {-1, -1};
root = t1[root][i];
}
return pos1[root];
}
int timer2 = 0;
vector<int> pos2[4 * N];
void add2(string s, int idx) {
int root = 0;
for(char c: s) {
int i = id(c);
if (t2[root][i] == 0) t2[root][i] = ++timer2;
root = t2[root][i];
pos2[root].push_back(idx);
}
}
int query2(string s, int l, int r) {
int root = 0;
for(char c: s) {
int i = id(c);
if (t2[root][i] == 0) return 0;
root = t2[root][i];
}
int cnt = upper_bound(ALL(pos2[root]), r) - pos2[root].begin() - 1;
cnt -= lower_bound(ALL(pos2[root]), l) - pos2[root].begin() - 1;
return cnt;
}
void read() {
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
}
void solve() {
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++) {
string s = a[i];
add1(s, i);
reverse(ALL(s));
add2(s, i);
}
while(q--) {
string p, q; cin >> p >> q;
pair<int, int> pos = query1(p);
int ans = 0;
if (pos != mp(-1, -1)) {
reverse(ALL(q));
// cerr << pos.fi << ' ' << pos.se << endl;
ans = query2(q, pos.fi, pos.se);
}
cout << ans << endl;
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
int test = 1;
// cin >> test;
while(test--) {
read();
solve();
}
return 0;
}
