#define _CRT_SECURE_NO_DEPRECATE
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using str = string;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;
// pairs
// #define mp make_pair
#define f first
#define s second
// vectors
// size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
// #define rtn return
#define lb lower_bound
#define ub upper_bound
/* Some Codes Skipped */
// loops
#define FOR(i,a,b) for (int (i) = (a); (i) < (b); ++(i))
#define REP(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int (i) = (b)-1; (i) >= (a); --(i))
#define PER(i,a) ROF(i,0,a)
#define rep(a) REP(_,a)
#define each(a,x) for (auto& a: x)
const int MOD = 1e9+7;
const int MX = 2e5+5;
const ll INF = 1e18;
const db PI = acos((db)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem
tcT> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; }
tcT> void remDup(vector<T>& v) { // sort and remove duplicates
sort(all(v)); v.erase(unique(all(v)),end(v)); }
// Some Codes Skipped
inline namespace FileIO {
void setIn(str s) {freopen(s.c_str(),"r", stdin);}
void setOut(str s) {freopen(s.c_str(),"w", stdout);}
void setIO() {
cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams
// cin.exceptions(cin.failbit);
// throws exception when do smth illegal
// ex. try to read letter into int
// setIn("test.txt"), setOut("output.txt"); // for old USACO
}
}
const int N=2001000;
const int MAX_VALUE=4;
struct Node {
public:
Node* child[MAX_VALUE];
int exist, cnt, num;
int l, r;
vector<int> indexes;
Node(){
this->exist=0; this->cnt=0; this->num=0;
this->l=N; this->r=-1;
for(int i=0;i<MAX_VALUE;++i) this->child[i]=NULL;
}
};
map<char, int> index2;
struct Trie {
public:
Node* root;
Trie(){
root=new Node();
}
};
Trie* preTrie;
Trie* sufTrie;
void addString(string s, int stt){
Node* root=preTrie->root;
for(int i=0;i<s.size();++i){
root->cnt+=1;
root->l=min(root->l, stt);
root->r=max(root->r, stt);
int ind=index2[s[i]];
if(root->child[ind]==NULL){
root->child[ind]=new Node();
}
root=root->child[ind];
}
root->cnt+=1;
root->exist+=1;
root->l=min(root->l, stt);
root->r=max(root->r, stt);
root=sufTrie->root;
for(int i=s.size()-1;i>=0;--i){
root->cnt+=1;
root->indexes.push_back(stt);
int ind=index2[s[i]];
if(root->child[ind]==NULL){
root->child[ind]=new Node();
}
root=root->child[ind];
}
root->cnt+=1;
root->exist+=1;
root->indexes.push_back(stt);
}
struct Item {
public:
Node* node;
int n;
Item(Node* node, int n){
this->node=node;
this->n=n;
}
};
int stringWithPreAndSuf(string p, string q){
Node* root=preTrie->root;
for(int i=0;i<p.size();++i){
int ind=index2[p[i]];
if(root->child[ind]==NULL) return 0;
root=root->child[ind];
}
Node* root2=sufTrie->root;
for(int i=q.size()-1;i>=0;--i){
int ind=index2[q[i]];
if(root2->child[ind]==NULL) return 0;
root2=root2->child[ind];
}
auto left=lower_bound(root2->indexes.begin(), root2->indexes.end(), root->l);
auto right=upper_bound(root2->indexes.begin(), root2->indexes.end(), root->r);
if(left==root2->indexes.end()){
return 0;
}
int ans=right-left;
return ans;
}
void solve(int tc){
preTrie=new Trie();
sufTrie=new Trie();
vector<string> v;
int n, m; cin>>n>>m;
for(int i=0;i<n;++i){
string s; cin>>s;
v.push_back(s);
}
sort(v.begin(), v.end());
for(int i=0;i<n;++i){
addString(v[i], i);
}
for(int i=0;i<m;++i){
string p, q; cin>>p>>q;
cout<<stringWithPreAndSuf(p, q)<<"\n";
}
}
int main() {
index2['A']=0;
index2['C']=1;
index2['G']=2;
index2['U']=3;
setIO();
int tc=1;
// cin>>tc;
for(int i=1;i<=tc;++i){
solve(i);
}
}
