// cre: Nguyen Hoang Hung - Train VOI 2024
#include <bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define EACH(it,a) for(__typeof(a->begin()) it = a->begin(); it != a->end(); ++it)
#define debug(x) { cerr << #x << " = "; cerr << (x) << endl; }
#define PR(a,n) { cerr << #a << " = "; FOR(_,1,n) cerr << a[_] << ' '; cerr << endl; }
#define PR0(a,n) { cerr << #a << " = "; REP(_,n) cerr << a[_] << ' '; cerr << endl; }
#define bit(X, i) ((X >> i) & 1)
#define cntbit(X) __builtin_popcountll(X)
#define fi first
#define se second
#define pb push_back
#define all(X) begin(X), end(X)
#define SZ(X) ((int)(X).size())
#define RR(X) X->resize(unique(all(X)) - begin(X))
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
template <typename T>
bool maximize(T &x, T y)
{
if(x < y)
x = y;
else
return 0;
return 1;
}
template <typename T>
bool minimize(T &x, T y)
{
if(x > y)
x = y;
else
return 0;
return 1;
}
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
ll Rand(ll l, ll r) { return l + rand() % (r - l + 1); }
const int maxN = 2e6;
const ll inf = 1e18+7;
const int MOD = 1e9 + 7;
const double PI = acos(-1);
/*
-------------------------------------------------------------------------------------
END OF TEMPLATE
-------------------------------------------------------------------------------------
Nguyen Hoang Hung - catlover
Training for VOI24 gold medal
-------------------------------------------------------------------------------------
*/
int N, M, pos[maxN];
string s[maxN];
int convert(char c) {
if(c == 'A') return 0;
if(c == 'G') return 1;
if(c == 'C') return 2;
return 3;
}
//////////////////////////////////////////////////
/**
BUILD TRIE
**/
struct Trie
{
Trie *child[4];
int tin, tout;
vector<int> vt;
Trie()
{
FOR(i, 0, 3) child[i] = NULL;
tin = tout = 0;
vt.resize(0);
}
};
Trie T, T_rev;
void add(string s, int id)
{
Trie *p = &T;
FOR(i, 0, SZ(s)-1)
{
int c = convert(s[i]);
if (p->child[c] == NULL) p->child[c] = new Trie();
p = p->child[c];
}
p->vt.pb(id);
}
void add_rev(string s, int id)
{
Trie *p = &T_rev;
FOR(i, 0, SZ(s)-1)
{
int c = convert(s[i]);
if (p->child[c] == NULL) p->child[c] = new Trie();
p = p->child[c];
p->vt.pb(pos[id]);
}
}
//////////////////////////////////////////////////
/**
EULER TOUR
**/
int Time = 0;
void dfs(Trie *p)
{
p->tin = ++Time;
if(p->vt.size())
{
for(auto x : p->vt)
pos[x] = Time;
}
FOR(i, 0, 3)
{
if(p->child[i] == NULL) continue;
dfs(p->child[i]);
}
p->tout = Time;
}
void dfs_Rev(Trie *p)
{
sort(all(p->vt));
FOR(i, 0, 3)
{
if (p->child[i] == NULL) continue;
dfs_Rev(p->child[i]);
}
}
pii getRange(string s)
{
Trie *p = &T;
FOR(i, 0, SZ(s)-1)
{
int c = convert(s[i]);
if (p->child[c] == NULL) return make_pair(0, 0);
p = p->child[c];
}
return make_pair(p->tin, p->tout);
}
int getAns(string s, pii Range)
{
Trie *p = &T_rev;
FOR(i, 0, SZ(s)-1)
{
int c = convert(s[i]);
if (p->child[c] == NULL) return 0;
p = p->child[c];
}
int l = lower_bound(all(p->vt), Range.fi) - p->vt.begin();
int r = upper_bound(all(p->vt), Range.se) - p->vt.begin()-1;
return (r - l + 1);
}
void solve() {
cin >> N >> M;
FOR(i, 1, N) cin >> s[i];
FOR(i, 1, N) add(s[i], i);
dfs(&T);
FOR(i, 1, N) reverse(all(s[i]));
FOR(i, 1, N) add_rev(s[i], i);
dfs_Rev(&T_rev);
while(M --> 0)
{
string P, Q; cin >> P >> Q;
reverse(all(Q));
pii R = getRange(P);
// cout << R.fi << ' ' << R.se << endl;
cout << getAns(Q, R) << '\n';
}
}
void solve_TestCase() {
int testcase; cin >> testcase;
while(testcase --> 0)
{
solve();
}
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
file("RNA");
// solve_TestCase();
solve();
cerr << "\nTime : " << clock()/1000.0 << "s\n";
return 0;
}
