#include <bits/stdc++.h>
using namespace std;

int n,q;
string w[100010];

template<int char_size>
struct Trie{
	struct Node{
		int nxt[char_size];
 
		int childs;
		bool isExist;
 
		Node() : childs(0),isExist(false){
			fill(nxt,nxt + char_size,-1);
		}
	};
 
	static inline int ctoi_default(char c){
		return c - 'a';
	}
 
	using F = function<int(char)>;
	F ctoi;
	vector<Node> nodes;
 
	Trie(F ctoi = ctoi_default) : ctoi(ctoi){
		nodes.emplace_back();
	}
 
	inline int &next(int pos,int c){
		return nodes[pos].nxt[c];
	}
 
	inline int &next(int pos,char c){
		return next(pos,ctoi(c));
	}
 
	void add(const string &s){
		int pos = 0;
		for(int i = 0;i < s.length();i++){
			const int c = ctoi(s[i]);
			if(next(pos,c) == -1){
				next(pos,c) = nodes.size();
				nodes.emplace_back();
			}
			pos = next(pos,c);
			nodes[pos].childs++;
		}
		nodes[pos].isExist = true;
	}
 
	int find(const string &s){
		int pos = 0;
		for(int i = 0;i < s.length();i++){
			const int c = ctoi(s[i]);
			if(next(pos,c) == -1) return -1;
			pos = next(pos,c);
		}
		return pos;
	}
};

struct SegTree{
	int n,seg;
	//vector<Trie<26>> trie;
	vector<vector<string>> dat;
	SegTree(int siz) : n(siz),seg(1){
		while(seg < n) seg *= 2;
		dat.resize(seg * 2 - 1);
		//trie.resize(seg * 2 - 1);
		for(int i = 0;i < n;i++){
			string v = w[i];
			reverse(v.begin(),v.end());
			dat[i + seg - 1].push_back(v);
			//trie[i + seg - 1].add(v);
		}
		for(int i = seg - 2;i >= 0;i--){
			dat[i].insert(dat[i].end(),dat[i * 2 + 1].begin(),dat[i * 2 + 1].end());
			dat[i].insert(dat[i].end(),dat[i * 2 + 2].begin(),dat[i * 2 + 2].end());
			sort(dat[i].begin(),dat[i].end());
			//for(const string &s : dat[i]) trie[i].add(s);
		}
	}
	int get(const string &s,int a = 0,int b = -1,int k = 0,int l = 0,int r = -1){
		if(b == -1) b = seg;
		if(r == -1) r = seg;
		if(b <= l || r <= a) return 0;
		if(a <= l && r <= b){
			int lind = lower_bound(dat[k].begin(),dat[k].end(),s) - dat[k].begin();
			string t = s; t.back()++;
			int rind = lower_bound(dat[k].begin(),dat[k].end(),t) - dat[k].begin();
			return rind - lind;
		}
		return get(s,a,b,k * 2 + 1,l,(l + r) / 2) + get(s,a,b,k * 2 + 2,(l + r) / 2,r); //do
	}
};

signed main(){
	cin >> n >> q;
	for(int i = 0;i < n;i++) cin >> w[i];
	sort(w,w + n);
	SegTree seg(n);
	for(int i = 0;i < q;i++){
		string p,s;
		cin >> p >> s;
		reverse(s.begin(),s.end());
		int l = lower_bound(w,w + n,p) - w;
		p.back()++;
		int r = lower_bound(w,w + n,p) - w;
		cout << seg.get(s,l,r) << endl;
	}
}
