//******************/
//* I<3 C++ */
//* I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S long longERESTING*/
//* I LOVE PROGRAM!*/
//* IN CONTESTS */
//* GET SCORE */
//* AC CODE */
//* LET'S */
//* GO */
//* Written by: */
//* Duc Minh */
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define file(name) freopen(name".inp", "r", stdin);\
freopen(name".out", "w", stdout);
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define all(a) a.begin(),a.end()
#define endl "\n"
#define all1(a) a+1,a+n+1
#define unordered_map map
// #define push_back emplace_back
// #define gcd(a,b) __gcd(a,b);
// #define lcm(a,b) (a*b)/gcd(a,b);
const long long INF = (long long)1e18;
const long long MOD = (long long)1e9+7;
const long long MODD = 1e9; /// 998244353
const long long maxN = 25009;
///--------------------------------
void solve();
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
// file("tbrackets");
long long t;
// cin >> t;
t=1;
while (t--){
solve();
}
cerr << "Time elapsed: " << TIME << "s.\n";
cerr << "ducminh" << "\n";
return 0;
}
///--------------------[PROBLEM SOLUTION]--------------------///
int val(char c) {
switch(c) {
case 'A': return 0;
case 'G': return 1;
case 'C': return 2;
default: return 3;
}
}
int n,q;
struct Trie {
struct Node{
Node* child[4];
int cnt,exist,l,r;
Node() {
for (int i = 0; i < 4; i++) child[i] = nullptr;
cnt=exist==0;
l=n; r=0;
}
};
Node* root= new Node();
void insert(string x, int id){
Node* p=root;
for (char ch: x){
int c=val(ch);
if (p->child[c]==nullptr){
p->child[c]=new Node();
}
p=p->child[c];
p->cnt++;
p->l=min(p->l,id);
p->r=max(p->r,id);
}
p->exist++;
}
pair<int,int> check(string s) {
Node* p = root;
pair<int,int> ans={0,n};
for (auto f : s) {
int c = val(f);
if (p->child[c] == nullptr) return ans;
p = p->child[c];
ans.first=max(ans.first,p->l);
ans.second=min(ans.second,p->r);
}
return ans;
}
};
struct reverseTrie {
struct Node{
Node* child[4];
int cnt,exist;
vector<int> luu;
Node() {
for (int i = 0; i < 4; i++) child[i] = nullptr;
cnt=exist==0;
}
};
Node* root= new Node();
void insert(string x, int id){
Node* p=root;
reverse(all(x));
for (char ch: x){
int c=val(ch);
if (p->child[c]==nullptr){
p->child[c]=new Node();
}
p=p->child[c];
p->cnt++;
p->luu.push_back(id);
}
p->exist++;
}
int query(string s, pair<int,int> range) {
Node* p = root;
pair<int,int> ans={0,n};
reverse(all(s));
for (auto f : s) {
int c = val(f);
if (p->child[c] == nullptr) return 0;
p = p->child[c];
}
int l=lower_bound(all(p->luu),range.first)-(p->luu).begin();
int r=upper_bound(all(p->luu),range.second)-(p->luu).begin()-1;
return r-l+1;
}
};
Trie a;
reverseTrie b;
void solve(){
string s[100009];
cin >> n >> q;
for (int i=1; i<=n; i++){
cin >> s[i];
}
sort(s+1,s+n+1);
for (int i=1; i<=n; i++) a.insert(s[i],i),b.insert(s[i],i);
while (q--){
string s1,s2;
cin >> s1 >> s2;
auto tam=a.check(s1);
if (!tam.first) {cout << 0 << "\n"; continue;}
cout << b.query(s2,tam) << "\n";
}
}
