#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i = l ; i <= r ; ++i)
#define FORD(i,l,r) for(int i = l ; i >= r ; --i)
#define open(FILENAME) freopen(FILENAME".inp","r",stdin);
#define close(FILENAME) freopen(FILENAME".out","w",stdout);
#define ll long long
#define ld long double
#define fi first
#define se second
#define BIT(n,i) ((n >> i) & (1ll))
#define MASK(i) ((1ll) << i)
#define ii pair<int,int>
#define li pair<ll ,int>
#define name "test"
#define pb push_back
#define all(x) (x).begin(), (x).end()
using namespace std;
const int N = 1e5;
const int bl = 450;
const int INF = 2e9;
const ll LINF = 1e18;
const int Mod = 1e9 + 7;
int n,q;
string s[N + 3];
int cal(char c){
if(c == 'A') return 0;
if(c == 'U') return 1;
if(c == 'G') return 2;
if(c == 'C') return 3;
}
struct trie{
struct node{
node* child[4];
int l ,r;
node(){
FOR(i , 0 , 3) child[i] = NULL;
l = N , r = 0;
}
};
struct node1{
node1* child[4];
vector<int> id;
node1(){
FOR(i , 0 , 3) child[i] = NULL;
id.clear();
}
};
node* root = new node();
node1* root1 = new node1();
void update(string &s ,int pos){
node* p = root;
FOR(i , 0 , s.size() - 1){
int id1 = cal(s[i]);
if(p -> child[id1] == NULL) p -> child[id1] = new node();
p = p -> child[id1];
p -> l = min(p -> l , pos);
p -> r = max(p -> r , pos);
}
}
void update1(string &s ,int pos){
node1* p1 = root1;
reverse(all(s));
FOR(i , 0 , s.size() - 1){
int id1 = cal(s[i]);
if(p1 -> child[id1] == NULL)
p1 -> child[id1] = new node1();
p1 = p1 -> child[id1];
p1 -> id.pb(pos);
}
}
ii get(string &s){
node* p = root;
FOR(i , 0 , s.size() - 1){
int id1 = cal(s[i]);
if(p -> child[id1] == NULL) return {-1 , -1};
p = p -> child[id1];
}
return {p -> l , p -> r};
}
int get1(string &s , ii p1){
node1* p = root1;
int l = p1.fi;
int r = p1.se;
if(l == -1) return 0;
FOR(i , 0 , s.size() - 1){
int id1 = cal(s[i]);
if(p -> child[id1] == NULL) return 0;
p = p -> child[id1];
}
return upper_bound(all(p -> id) , r) - lower_bound(all(p -> id) , l);
}
} t;
void solve(){
cin >> n >> q;
FOR(i , 1 , n) cin >> s[i];
sort(s + 1 , s + n + 1);
FOR(i , 1 , n){
t.update(s[i] , i);
t.update1(s[i] , i);
}
while(q--){
string s2,s3;
cin >> s2 >> s3;
reverse(all(s3));
cout << t.get1(s3 , t.get(s2)) << "\n";
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int usaco = 0;
if(fopen(name".inp" , "r")){
open(name);
close(name);
}
solve();
return 0;
}
