#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#pragma GCC optimize ("Ofast")
#define all(x) x.begin() , x.end()
#define gcd __gcd
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
struct piii {
int first , second , third;
};
const ll MAX_N = 5e3 + 20 , md = 1100000123;
ll tav(ll n , ll k){
ll res = 1;
while(k > 0){
if(k & 1){
res *= n;
}
n *= n;
k /= 2;
}
return res;
}
vector<ll> ph[MAX_N] , sh[MAX_N];
ll oh[MAX_N] , qh[MAX_N] , sz[MAX_N] , osz[MAX_N] , qsz[MAX_N];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n , m;
cin>>n>>m;
if(n >= MAX_N || m >= MAX_N) return 0;
for(int i = 0 ; i < n ; i++){
string s;
cin>>s;
ll h = s.size(); sz[i] = h;
for(int j = 0 ; j < h ; j++){
if(s[j] == 'A'){
s[j] = 0;
}
if(s[j] == 'C'){
s[j] = 1;
}
if(s[j] == 'G'){
s[j] = 2;
}
if(s[j] == 'U'){
s[j] = 3;
}
}
ll t = 1 , hash = 0;
ph[i].resize(h); sh[i].resize(h);
for(int j = 0 ; j < h ; j++){
hash += 1ll * t * s[j]; hash %= md;
t *= 4; t %= md;
ph[i][j] = hash;
}
hash = 0; t = 1;
for(int j = h - 1 ; j >= 0 ; j--){
hash += 1ll * t * s[j]; hash %= md;
t *= 4; t %= md;
sh[i][j] = hash;
}
}
for(int i = 0 ; i < m ; i++){
string o , q;
cin>>o>>q;
ll hash = 0 , t = 1 , os = o.size() , qs = q.size(); osz[i] = os; qsz[i] = qs;
for(int j = 0 ; j < os ; j++){
if(o[j] == 'A'){
o[j] = 0;
}
if(o[j] == 'C'){
o[j] = 1;
}
if(o[j] == 'G'){
o[j] = 2;
}
if(o[j] == 'U'){
o[j] = 3;
}
}
for(int j = 0 ; j < qs ; j++){
if(q[j] == 'A'){
q[j] = 0;
}
if(q[j] == 'C'){
q[j] = 1;
}
if(q[j] == 'G'){
q[j] = 2;
}
if(q[j] == 'U'){
q[j] = 3;
}
}
for(int j = 0 ; j < os ; j++){
hash += 1ll * t * o[j]; hash %= md;
t *= 4; t %= md;
}
oh[i] = hash;
hash = 0; t = 1;
for(int j = qs - 1 ; j >= 0 ; j--){
hash += 1ll * t * q[j]; hash %= md;
t *= 4; t %= md;
}
qh[i] = hash;
}
for(int i = 0 ; i < m ; i++){
ll cnt = 0;
for(int j = 0 ; j < n ; j++){
if(osz[i] > sz[j] || qsz[i] > sz[j]) continue;
if(oh[i] != ph[j][osz[i] - 1]) continue;
if(qh[i] != sh[j][sz[j] - qsz[i]]) continue;
cnt++;
}
cout<<cnt<<'\n';
}
return 0;
}
