#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 2e6 + 5;
int f[N];
void upd(int i,int h) {
for (;i <= N;i += i&(-i))
f[i] += h;
}
int que(int i) {
int ans = 0;
for (;i;i -= i&(-i))
ans += f[i];
return ans;
}
struct trie {
trie * t[4];
int pos;
trie(void) {
memset(t,0,sizeof(t));
pos = -1;
}
};
typedef trie * tr;
int g(char ch) {
return ch == 'A' ? 0 : ch == 'U' ? 1 : ch == 'G' ? 2 : 3;
}
void add(tr root,string str) {
auto cnt = root;
for (auto it : str) {
int ch = g(it);
if (!cnt->t[ch])
cnt->t[ch] = new trie();
cnt = cnt->t[ch];
}
}
void dfs(tr root,int S[],int F[],int &timer) {
if (!root)
return;
root->pos = ++timer;
S[root->pos] = timer;
for (int i = 0;i < 4;++i)
dfs(root->t[i],S,F,timer);
F[root->pos] = timer;
}
int get(tr root,string str) {
auto cnt = root;
for (auto it : str) {
int ch = g(it);
cnt = cnt->t[ch];
if (!cnt)
break;
}
if (!cnt)
return -1;
else
return cnt->pos;
}
tr T[2];
vi up[N];
vector < vi > qu[N];
int S[2][N];
int F[2][N];
int ans[N];
int main(void) {
T[0] = new trie();
T[1] = new trie();
int n,m;
cin>>n>>m;
vector < string > s(n);
for (auto & it : s) {
cin>>it;
add(T[0],it);
reverse(all(it));
add(T[1],it);
reverse(all(it));
}
int timer = 0;
dfs(T[0],S[0],F[0],timer);
timer = 0;
dfs(T[1],S[1],F[1],timer);
for (auto it : s) {
int x = get(T[0],it);
reverse(all(it));
int y = get(T[1],it);
up[S[0][x]].pb(S[1][y]);
}
for (int i = 1;i <= m;++i) {
string a,b;
cin>>a>>b;
reverse(all(b));
int x = get(T[0],a);
int y = get(T[1],b);
if (x == -1 || y == -1)
continue;
qu[S[0][x] - 1].pb({-1,S[1][y] - 1,F[1][y],i});
qu[F[0][x]].pb({1,S[1][y] - 1,F[1][y],i});
}
for (int i = 1;i < N;++i) {
for (auto it : up[i])
upd(it,1);
for (auto it : qu[i])
ans[it[3]] += it[0] * (que(it[2]) - que(it[1]));
}
for (int i = 1;i <= m;++i)
cout << ans[i] << '\n';
return 0;
}
