#include <bits/stdc++.h>
#define int long long
#define dim 200006
#define mod 666013//1000000007
using namespace std;
ifstream fin ("trie.in");
ofstream fout("trie.out");
string s;
int n,indice,v[dim],unu[dim],ans[dim],trans[300];
vector<int>lin[3];
struct trie
{
int st,dr;
vector<int> id;
trie *kids[4];
trie ()
{
for (int i=0; i<=3; i++)
kids[i]=nullptr;
}
};
trie* insert (trie *node,int index)
{
if (node==nullptr)
node=new trie;
if (index==(int)s.size())
{
node->id.push_back(indice);
return node;
}
node->kids[trans[s[index]]]=insert(node->kids[trans[s[index]]],index+1);
return node;
}
string intoarce (string s)
{
int i=0,j=s.size()-1;
for (; i<j; i++,j--)
swap(s[i],s[j]);
return s;
}
trie *dfs (trie *node)
{
if (node==nullptr)
return nullptr;
node->st=(int)lin[indice].size();
for (auto x:node->id)
lin[indice].push_back(x);
for (int i=0; i<4; i++)
node->kids[i]=dfs(node->kids[i]);
node->dr=(int)lin[indice].size()-1;
return node;
}
pair<int,int> get (trie *node,int index)
{
if (node==nullptr)
return {-1,-1};
if (index==(int)s.size())
return {node->st,node->dr};
else return get(node->kids[trans[s[index]]],index+1);
}
struct element
{
int l,r,index,coef;
};
vector<element> query[dim];
void update (int poz, int val)
{
for (int i=poz; i<=n; i=i+(i&-i))
v[i]=v[i]+val;
}
int ask (int poz)
{
int sum=0;
for (int i=poz; i>=1; i=i-(i&-i))
sum+=v[i];
return sum;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
trans['G']=1,trans['C']=2,trans['U']=3;
int t,i;
trie *pr=nullptr;
trie *sf=nullptr;
cin>>n>>t;
cin.get();
for (i=1; i<=n; i++)
{
cin>>s;
indice=i;
pr=insert(pr,0);
s=intoarce(s);
sf=insert(sf,0);
}
lin[1].push_back(0);
lin[2].push_back(0);
indice=1;
pr=dfs(pr);
indice=2;
sf=dfs(sf);
for (i=1; i<=t; i++)
{
cin>>s;
pair<int,int>el1=get(pr,0);
cin>>s;
s=intoarce(s);
pair<int,int>el2=get(sf,0);
if (el1.first!=-1&&el2.first!=-1)
{
query[el2.first-1].push_back({el1.first,el1.second,i,-1});
query[el2.second].push_back({el1.first,el1.second,i,1});
}
}
for (i=1; i<=n; i++)
unu[lin[1][i]]=i;
for (i=1; i<=n; i++)
{
update(unu[lin[2][i]],1);
for (element q:query[i])
ans[q.index]+=q.coef*(ask(q.r)-ask(q.l-1));
}
for (i=1; i<=t; i++)
cout<<ans[i]<<'\n';
return 0;
}
