#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e6 + 5, inf = 1e9;
#define pb push_back
#define mp make_pair
#define ll long long
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define sz(x) (int)x.size()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
map<char, int> ma;
struct trie{
vi at[N];
int to[N][4];
int d = 1;
void add(string x, int idx){
int v = 0;
for(int i = 0; i < sz(x); i++){
if(!to[v][ma[x[i]]]){
to[v][ma[x[i]]] = d++;
}
v = to[v][ma[x[i]]];
at[v].pb(idx);
}
}
ii q1(string x){
int v = 0;
for(int i = 0; i < sz(x); i++){
if(!to[v][ma[x[i]]])return {-1, -1};
v = to[v][ma[x[i]]];
}
return {at[v][0], at[v].back()};
}
int q2(int l, int r, string x){
int v = 0;
for(int i = 0; i < sz(x); i++){
if(!to[v][ma[x[i]]])return 0;
v = to[v][ma[x[i]]];
}
return upper_bound(all(at[v]), r) - lower_bound(all(at[v]), l);
}
}a, b;
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n, m;
cin >> n >> m;
ma['A'] = 0;
ma['C'] = 1;
ma['G'] = 2;
ma['U'] = 3;
vector<string> v;
for(int i = 0; i < n; i++){
string s;
cin >> s;
v.pb(s);
}
sort(all(v));
for(int i = 0; i < n; i++){
a.add(v[i], i);
reverse(all(v[i]));
b.add(v[i], i);
}
for(int i = 0; i < m; i++){
string p, q;
cin >> p >> q;
reverse(all(q));
ii res1 = a.q1(p);
if(res1 == mp(-1, -1)){
cout << "0\n";
continue;
}
cout << b.q2(res1.ff, res1.ss, q) << '\n';
}
return 0;
}
