#include <bits/stdc++.h>
#include <istream>
#define pb push_back
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define ll long long
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
// #define int ll
using namespace std;
const int N = 2e6 + 5;
string s[N];
map <int,int> mp;
int r1[N],r2[N];
int t[N][5],cnt1 = 1,cnt2 = 1,timer1,tin1[N],tout1[N];
int timer2,tin2[N],tout2[N],S[N][5];
vector <pii> vec1,vec2;
vector <int> arr[N],T[4*N];
void add1(string str,int id){
int root = 1;
for (int i = 0; i < str.size(); i++){
int b = mp[str[i]];
if (!t[root][b]){
t[root][b] = ++cnt1;
}
root = t[root][b];
}
r1[id] = root;
}
int getprefix(string str){
int root = 1;
for (int i = 0; i < str.size(); i++){
int b = mp[str[i]];
if (!t[root][b]) return -1;
root = t[root][b];
}
return root;
}
int getsuffix(string str){
int root = 1;
for (int i = 0; i < str.size(); i++){
int b = mp[str[i]];
if (!S[root][b]) return -1;
root = S[root][b];
}
return root;
}
void add2(string str,int id){
int root = 1;
for (int i = 0; i < str.size(); i++){
int b = mp[str[i]];
if (!S[root][b]){
S[root][b] = ++cnt2;
}
root = S[root][b];
}
r2[id] = root;
}
void dfs1(int x){
tin1[x] = ++timer1;
for (int i = 1; i <= 4; i++){
if (t[x][i]) dfs1(t[x][i]);
}
tout1[x] = timer1;
}
void dfs2(int x){
tin2[x] = ++timer2;
for (int i = 1; i <= 4; i++){
if (S[x][i]) dfs2(S[x][i]);
}
tout2[x] = timer2;
}
vector <int> merge(vector <int> x, vector <int> y){
vector <int> ans;
if (!x.size()) return y;
if (!y.size()) return x;
int l1 = 0,l2 = 0;
while (l1 < x.size() || l2 < y.size()){
if (l1==x.size()){
ans.pb(y[l2++]);
continue;
}
if (l2 == y.size()){
ans.pb(x[l1++]);
continue;
}
if (x[l1] < y[l2]){
ans.pb(x[l1++]);
}else{
ans.pb(y[l2++]);
}
}
return ans;
}
void build(int h,int l,int r){
if (l == r){
T[h] = arr[l];
return;
}
build(left);
build(right);
T[h] = merge(T[h*2],T[h*2+1]);
}
int get(int h,int l,int r,int L,int R,int l2,int r2){
if (r < L || R < l) return 0;
if (L <= l && r <= R){
int res1 = -1,le = 0,ri = T[h].size() - 1;
while (le <= ri){
int mid = (le + ri) / 2;
if (T[h][mid] >= l2) {
res1 = mid;
ri = mid - 1;
}else{
le = mid + 1;
}
}
if(res1==-1) return 0;
int res2=-1; le = 0; ri = T[h].size() - 1;
while (le <= ri){
int mid = (le + ri) / 2;
if (T[h][mid] <= r2) {
res2 = mid;
le = mid + 1;
}else{
ri = mid - 1;
}
}
if(res2==-1) return 0;
return (res2 - res1 + 1);
}
return get(left,L,R,l2,r2) + get(right,L,R,l2,r2);
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
mp['A'] = 1;
mp['C'] = 2;
mp['G'] = 3;
mp['U'] = 4;
int n,m;
cin>>n>>m;
for (int i = 1; i <= n; i++){
cin >> s[i];
add1(s[i],i);
reverse(s[i].begin(),s[i].end());
add2(s[i],i);
}
dfs1(1);
dfs2(1);
for (int i = 1; i <= n; i++){
arr[tin2[r2[i]]].pb(tin1[r1[i]]);
}
int mm = tout2[1];
for (int i = 1; i <= mm; i++){
sort(arr[i].begin(),arr[i].end());
}
build(1,1,mm);
for (int i = 1; i <= m; i++){
string x,y;
cin>>x>>y;
int A = getprefix(x);
if (A == -1) {
cout<<0<<endl;
continue;
}
int l1 = tin1[A],r1 = tout1[A];
reverse(y.begin(),y.end());
int B = getsuffix(y);
if (B == -1){
cout<<0<<endl;
continue;
}
int l2 = tin2[B],r2 = tout2[B];
cout<<get(1,1,mm,l2,r2,l1,r1)<<endl;
}
}
