#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e5 + 9;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
string s[N],rs[N];
ll n,Q;
char Convert(char c){
if (c == 'A') return '0';
if (c == 'G') return '1';
if (c == 'C') return '2';
if (c == 'U') return '3';
}
void oper(string &s){
for (ll j = 0;j < s.size();j++) s[j] = Convert(s[j]);
}
struct Trie{
Trie *child[4];
ll l,r;
vector<ll> v;
Trie(){
l = inf; r = 0;
for (ll i = 0;i < 4;i++) child[i] = NULL;
}
void Add1(ll id,string &s,ll pos){
l = min(l,pos); r = max(r,pos);
if (id == s.size()) return;
ll x = s[id] - '0';
if (!child[x]) child[x] = new Trie;
child[x] -> Add1(id + 1,s,pos);
}
void Add2(ll id,string&s,ll pos){
v.push_back(pos);
if (id == s.size()) return;
ll x = s[id] - '0';
if (!child[x]) child[x] = new Trie;
child[x] -> Add2(id + 1,s,pos);
}
void TravelSort(){
sort(v.begin(),v.end());
for (ll i = 0;i < 4;i++) if (child[i])
child[i] -> TravelSort();
}
LL getPair(ll id,string&s){
if (id == s.size()) return {l,r};
ll x = s[id] - '0';
if (child[x]) return child[x] -> getPair(id + 1,s);
return {-1,-1};
}
ll GetAns(ll id,string &s,ll L,ll R){
if (id == s.size()){
//cout<<v.size()<<"x"; exit(0);
//for (auto i : v) cout<<i<<" "; exit(0);
ll p = lower_bound(v.begin(),v.end(),L) - v.begin();
ll q = upper_bound(v.begin(),v.end(),R) - v.begin() - 1;
return max(0,q - p + 1);
}
ll x = s[id] - '0';
if (child[x]) return child[x] -> GetAns(id + 1,s,L,R);
return 0;
}
};
string p,q;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define task "tst"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
//freopen(task".out", "w", stdout);
}
Trie Tree1,Tree2; /// 1 for origin 2 for reversed
cin>>n>>Q;
for (ll i = 1;i <= n;i++) cin>>s[i],oper(s[i]);
sort(s + 1,s + n + 1);
for (ll i = 1;i <= n;i++){
rs[i] = s[i];
reverse(rs[i].begin(),rs[i].end());
Tree1.Add1(0,s[i],i); Tree2.Add2(0,rs[i],i);
}
Tree2.TravelSort();
while(Q--){
cin>>p>>q; oper(p); oper(q);
reverse(q.begin(),q.end());
LL now = Tree1.getPair(0,p); //cout<<now.fs<<" "<<now.sc; return 0;
cout<<Tree2.GetAns(0,q,now.fs,now.sc)<<"\n";
}
}
