#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+5;
int n,q;
int tree1[maxn][5],tree2[maxn][5],cnt1=1,cnt2=1;
int fa1[maxn],dep1[maxn],siz1[maxn],hson1[maxn],l1[maxn],r1[maxn],l2[maxn],idfn[maxn],r2[maxn],dfn_cnt1,dfn_cnt2;
vector<int> item[maxn];// for tree 1
int plc[maxn];// for tree 2
struct Query{
	int plc,id;
};
vector<Query> query[maxn];
int ans[maxn];
struct BIT{
	int tree[maxn];
	inline int lbit(int x){
		return x&(-x);
	}
	void update(int plc,int val){
		for(int i=plc;i<=cnt2;i+=lbit(i)){
			tree[i]+=val;
		}
	}
	int query(int plc){
		if(!plc) return 0;
		int ret=0;
		for(int i=plc;i;i-=lbit(i)){
			ret+=tree[i];
		}
		return ret;
	}
} bit;
inline int id(char c){
	if(c=='A') return 1;
	if(c=='U') return 2;
	if(c=='G') return 3;
	return 4;
}
void insert1(string s,int ids){
	int p=1;
	for(int i=0;i<(int)s.size();i++){
		if(!tree1[p][id(s[i])]){
			tree1[p][id(s[i])]=++cnt1;
		}
		p=tree1[p][id(s[i])];
	}
	item[p].push_back(ids);
}
void insert2(string s,int ids){
	int p=1;
	for(int i=(int)s.size()-1;i>=0;i--){
		if(!tree2[p][id(s[i])]){
			tree2[p][id(s[i])]=++cnt2;
		}
		p=tree2[p][id(s[i])];
	}
	plc[ids]=p;
}
int search1(string s){
	int p=1;
	for(int i=0;i<(int)s.size();i++){
		if(!p) return 0;
		p=tree1[p][id(s[i])];
	}
	return p;	
}
int search2(string s){
	int p=1;
	for(int i=(int)s.size()-1;i>=0;i--){
		if(!p) return 0;
		p=tree2[p][id(s[i])];
	}
	return p;	
}
void dfs_t1(int u,int fath){
	l1[u]=++dfn_cnt1;
	idfn[dfn_cnt1]=u;
	fa1[u]=fath,dep1[u]=dep1[fath]+1;
	siz1[u]=item[u].size();
	for(int i=1;i<=4;i++){
		int v=tree1[u][i];
		if(v){
			dfs_t1(v,u);
			siz1[u]+=siz1[v];
			if(siz1[v]>=siz1[hson1[u]]){
				hson1[u]=v;
			}
		}
	}
	r1[u]=dfn_cnt1;
}
void dfs_t2(int u){
	l2[u]=++dfn_cnt2;
	for(int i=1;i<=4;i++){
		int v=tree2[u][i];
		if(v){
			dfs_t2(v);
		}
	}
	r2[u]=dfn_cnt2;
}
void merge_t1(int u,int type){
	for(int i=1;i<=4;i++){
		int v=tree1[u][i];
		if(v && v!=hson1[u]){
			merge_t1(v,0);
		}
	}
	if(hson1[u]){
		merge_t1(hson1[u],1);
		for(int i=l1[u];i<l1[hson1[u]];i++){
			for(int v:item[idfn[i]]){
				bit.update(l2[plc[v]],1);
			}
		}
		for(int i=r1[hson1[u]]+1;i<=r1[u];i++){
			for(int v:item[idfn[i]]){
				bit.update(l2[plc[v]],1);
			}		
		}
	}
	else{
		for(int i=l1[u];i<=r1[u];i++){
			for(int v:item[idfn[i]]){
				bit.update(l2[plc[v]],1);
			}
		}		
	}
	for(auto q:query[u]){
		ans[q.id]=bit.query(r2[q.plc])-bit.query(l2[q.plc]-1);
	}
	if(!type){
		for(int i=l1[u];i<=r1[u];i++){
			for(int v:item[idfn[i]]){
				bit.update(l2[plc[v]],-1);
			}
		}		
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		string s;cin>>s;
		insert1(s,i);
		insert2(s,i);
	}
	for(int i=1;i<=q;i++){
		string a,b;cin>>a>>b;
		int p1=search1(a),p2=search2(b);
		if(p1 && p2) query[p1].push_back((Query){p2,i});
	}
	dfs_t1(1,0);
	dfs_t2(1);
	merge_t1(1,1);
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<"\n";
	}
}