/* I can do this all day */
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;
const int N = 2e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;
const int sigma = 4;
ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }
mt19937 rng(time(nullptr));
struct Trie
{
int ptr, sub[N], nxt[sigma][N];
void clr()
{
for(int i = 0; i <= ptr; i ++)
{
sub[i] = 0;
for(int j = 0; j < sigma; j ++) nxt[j][i] = 0;
}
ptr = 0;
}
void add(string s)
{
int v = 0;
sub[v] ++;
for(int i = SZ(s) - 1; ~i; i --)
{
int ch = s[i] - 'a';
if(!nxt[ch][v])
{
nxt[ch][v] = ++ptr;
}
v = nxt[ch][v];
sub[v] ++;
assert(v > 0);
}
}
int query(string s)
{
int v = 0;
for(int i = SZ(s) - 1; ~i; i --)
{
int ch = s[i] - 'a';
if(!nxt[ch][v]) return 0;
v = nxt[ch][v];
}
return sub[v];
}
} DS;
int n, m, ptr, sum[N], Ans[N], nxt[sigma][N];
vector < int > exact[N], vec[N], Q[N];
string s[N], p[N], q[N];
void add(int id)
{
int v = 0;
vec[v].push_back(id);
sum[v] += SZ(s[id]);
for(int i = 0; i < SZ(s[id]); i ++)
{
int ch = s[id][i] - 'a';
if(!nxt[ch][v])
{
nxt[ch][v] = ++ptr;
}
v = nxt[ch][v];
sum[v] += SZ(s[id]);
vec[v].push_back(id);
}
exact[v].push_back(id);
}
int query(int id)
{
int v = 0;
for(int i = 0; i < SZ(p[id]); i ++)
{
int ch = p[id][i] - 'a';
if(!nxt[ch][v]) return -1;
v = nxt[ch][v];
}
return v;
}
bool cmp(int i, int j)
{
return sum[i] > sum[j];
}
void dfs(int v)
{
vector < int > nei;
for(int i = 0; i < sigma; i ++)
{
if(nxt[i][v])
{
nei.push_back(nxt[i][v]);
}
}
sort(all(nei), cmp);
for(int i = 1; i < SZ(nei); i ++)
{
dfs(nei[i]);
DS.clr();
}
if(SZ(nei))
{
dfs(nei[0]);
}
for(int i = 1; i < SZ(nei); i ++)
{
int u = nei[i];
for(auto id : vec[u])
{
DS.add(s[id]);
}
}
for(auto id : exact[v])
{
DS.add(s[id]);
}
for(auto id : Q[v])
{
Ans[id] = DS.query(q[id]);
}
}
inline int calc(char c)
{
if(c == 'A') return 0;
if(c == 'U') return 1;
if(c == 'C') return 2;
return 3;
}
int main()
{
fast_io;
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
cin >> s[i];
for(int j = 0; j < SZ(s[i]); j ++)
{
s[i][j] = 'a' + calc(s[i][j]);
}
add(i);
}
/*for(int i = 0; i <= ptr; i ++)
{
for(int j = 0; j < sigma; j ++)
{
printf("i = %d j = %d nxt = %d sum = %d\n", i, j, nxt[j][i], sum[i]);
}
}
*/
for(int i = 1; i <= m; i ++)
{
cin >> p[i] >> q[i];
for(int j = 0; j < SZ(p[i]); j ++)
{
p[i][j] = 'a' + calc(p[i][j]);
}
for(int j = 0; j < SZ(q[i]); j ++)
{
q[i][j] = 'a' + calc(q[i][j]);
}
int id = query(i);
if(id != -1)
{
Q[id].push_back(i);
}
}
dfs(0);
for(int i = 1; i <= m; i ++)
{
cout << Ans[i] << endl;
}
return 0;
}
/* check corner case(n = 1?), watch for negetive index or overflow */
