#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
const int N = 2e5 + 5;
//const int M = 2e6 + 5;
const int oo = 1e9;
int n, m;
string s[N], a[N], b[N];
char change(char c){
if(c == 'A') return '1';
if(c == 'C') return '2';
if(c == 'G') return '3';
return '4';
}
struct trie{
trie* child[8];
vector<int> w;
trie(){
for(int i = 1; i <= 4; i ++) child[i] = NULL;
w.clear();
}
};
trie* root;
void add(string &x,int id){
trie* p = root;
for(auto i : x){
int val = (i - '0');
if(p -> child[val] == NULL) p -> child[val] = new trie();
p = p -> child[val];
p -> w.push_back(id);
}
}
int query(string &x,int l,int r){
trie* p = root;
for(auto i : x){
int val = (i - '0');
if(p -> child[val] == NULL) return 0;
p = p -> child[val];
}
auto v = upper_bound(p -> w.begin(), p -> w.end(), r);
auto u = lower_bound(p -> w.begin(), p -> w.end(), l);
if(v == p -> w.begin()) return 0;
if(u == p -> w.end()) return 0;
v--;
int tu = u - p -> w.begin();
int tv = v - p -> w.begin();
if(tu <= tv) return tv - tu + 1;
return 0;
}
struct tree{
tree* child[8];
int mx, mi;
tree(){
for(int i = 1; i <= 4; i ++) child[i] = NULL;
mx = 0, mi = n + 1;
}
};
tree* wr;
void update(string &x,int id){
tree* p = wr;
for(auto i : x){
int val = (i - '0');
if(p -> child[val] == NULL) p -> child[val] = new tree();
p = p -> child[val];
p -> mx = max(p -> mx, id);
p -> mi = min(p -> mi, id);
}
}
pair<int,int> get(string &x){
tree* p = wr;
for(auto i : x){
int val = (i - '0');
if(p -> child[val] == NULL) return {0, 0};
p = p -> child[val];
}
return {p -> mi, p -> mx};
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
root = new trie();
wr = new tree();
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> s[i];
for(int j = 0; j < s[i].size(); j ++){
s[i][j] = change(s[i][j]);
}
}
sort(s + 1, s + n + 1);
for(int i = 1; i <= n; i ++){
update(s[i], i);
string hk = s[i];
reverse(hk.begin(), hk.end());
add(hk, i);
}
for(int i = 1; i <= m; i ++){
cin >> a[i] >> b[i];
for(int j = 0; j < a[i].size(); j ++) a[i][j] = change(a[i][j]);
for(int j = 0; j < b[i].size(); j ++) b[i][j] = change(b[i][j]);
pair<int,int> kq = get(a[i]);
if(!kq.first){
cout << 0 << "\n";
continue;
}
reverse(b[i].begin(), b[i].end());
cout << query(b[i], kq.first, kq.second) << "\n";
}
}
