#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
const ll LINF = (ll)INF * INF;
#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod)
#define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'
#define MAXN 100100
#define MAXL 2000100
int n, m;
vector<int> s[MAXN];
int sttime[MAXL], fntime[MAXL], timer;
int trie[MAXL][4];
int tn = 1;
int suftrie[MAXL][4];
int stn = 1;
int strend[MAXN];
vector<int> sts[MAXL];
inline void str2vec(const string &s, vector<int> &v)
{
for (char c : s)
{
if (c == 'A')
v.pb(0);
else if (c == 'G')
v.pb(1);
else if (c == 'C')
v.pb(2);
else // U
v.pb(3);
}
}
void add(const vector<int> &s, bool rev, int ind, int cld[MAXL][4])
{
int &cnt = (rev ? stn : tn);
int dir = (rev ? -1 : 1);
int beg = 0;
int end = s.size() - 1;
if (rev)
swap(beg, end);
int v = 1;
for (int i = beg; (rev && i >= end) || (!rev && i <= end); i += dir)
{
if (rev)
sts[v].pb(sttime[strend[ind]]);
int u = s[i];
if (!cld[v][u])
{
cnt++;
cld[v][u] = cnt;
}
v = cld[v][u];
}
if (rev)
sts[v].pb(sttime[strend[ind]]);
if (!rev)
strend[ind] = v;
}
void dfs(int v)
{
sttime[v] = timer++;
FOR(i, 0, 4)
{
if (!trie[v][i])
continue;
dfs(trie[v][i]);
}
fntime[v] = timer;
}
int _find(const vector<int> &s, int trie[MAXL][4])
{
int v = 1;
for (int u : s)
{
if (!trie[v][u])
{
return -1;
}
v = trie[v][u];
}
return v;
}
int32_t main(void)
{
fast_io;
cin >> n >> m;
FOR(i, 0, n)
{
string si;
cin >> si;
str2vec(si, s[i]);
add(s[i], false, i, trie);
}
dfs(1);
FOR(i, 0, n)
{
add(s[i], true, i, suftrie);
}
FOR(i, 1, stn + 1)
{
sort(all(sts[i]));
}
while (m--)
{
string p, q;
cin >> p >> q;
vector<int> pv, qv;
str2vec(p, pv);
str2vec(q, qv);
reverse(all(qv));
int lv = _find(pv, trie);
int rv = _find(qv, suftrie);
if (lv < 0 || rv < 0)
{
cout << 0 << endl;
continue;
}
auto it1 = lower_bound(all(sts[rv]), sttime[lv]);
auto it2 = lower_bound(all(sts[rv]), fntime[lv]);
int ans = it2 - it1;
cout << ans << endl;
}
return 0;
}
