//e tach VOI huhu
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5+5;
int n,m,sta[20*N],ed[20*N],child[20*N][4][2],cnt = 0;
string a[N],p[N],q[N];
vector<int>kaori[20*N];
int val(char x){
if(x == 'A') return 0;
if(x == 'G') return 1;
if(x == 'C') return 2;
if(x == 'U') return 3;
}
void add(int id, int id1, string s){
int u = 0;
for(auto it: s){
int v = val(it);
if(!child[u][v][id]) child[u][v][id] = ++cnt;
u = child[u][v][id];
if(id == 1) kaori[u].push_back(id1);
if(id == 0){
if(sta[u] == 0) sta[u] = id1;
ed[u] = id1;
}
}
}
int get(int id, string s){
int u = 0;
for(auto it: s){
int v = val(it);
if(!child[u][v][id]) return 0;
u = child[u][v][id];
}
return u;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a+1,a+n+1);
for(int i = 1; i <= n; i++){
add(0,i,a[i]);
reverse(a[i].begin(),a[i].end());
add(1,i,a[i]);
}
for(int i = 1; i <= m; i++){
cin >> p[i] >> q[i];
int emilia = get(0,p[i]);
reverse(q[i].begin(),q[i].end());
int rem = get(1,q[i]);
int res1 = upper_bound(kaori[rem].begin(),kaori[rem].end(),ed[emilia])-kaori[rem].begin();
int res2 = lower_bound(kaori[rem].begin(),kaori[rem].end(),sta[emilia])-kaori[rem].begin();
cout << res1-res2 << "\n";
}
}
