#define lb(x) (x&-x)
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define swap(a,b) (a^=b^=a^=b)

using namespace std;
using i64 = long long;

typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
void chmin(int &x, int c) {
  x = min(x, c);
}
void chmax(int &x, int c) {
  x = max(x, c);
}

namespace fast_IO{
#define IOSIZE 100000
int precision=3,POW[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};char ibuf[IOSIZE],obuf[IOSIZE],*p1=ibuf,*p2=ibuf,*p3=obuf;
#ifdef ONLINE_JUDGE
#define getchar()((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x)((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch)(ch>47&&ch<58)
#define isspace(ch)(ch<33)
#endif
template<typename T>inline T read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)&&(ch!=EOF))if(ch==45)w=-1;if(ch==EOF)return 0;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*w;}template<typename T>inline bool read(T&s){s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)&&(ch!=EOF))if(ch==45)w=-1;if(ch==EOF)return 0;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*=w,1;}inline bool read(char&s){while(s=getchar(),isspace(s));return 1;}inline bool read(char*s){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return 0;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return 1;}template<typename T>inline void print(T x){if(x<0)putchar(45),x=-x;if(x>9)print(x/10);putchar(x%10+48);}inline void print(char x){putchar(x);}inline void print(char*x){while(*x)putchar(*x++);}inline void print(const char*x){for(int i=0;x[i];i++)putchar(x[i]);}inline bool read(std::string&s){s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return 0;while(!isspace(ch))s+=ch,ch=getchar();return 1;}inline void print(std::string x){for(int i=0,n=x.size();i<n;i++)putchar(x[i]);}inline bool read(bool&b){char ch;while(ch=getchar(),isspace(ch));b=ch^48;return 1;}inline void print(bool b){putchar(b+48);}inline bool read(double&x){int a=0,b=0;char ch=getchar();bool f=0;while(ch<48||ch>57){if(ch==45)f=1;ch=getchar();}while(47<ch&&ch<58){a=(a<<1)+(a<<3)+(ch^48);ch=getchar();}if(ch!=46){x=f?-a:a;return 1;}ch=getchar();while(47<ch&&ch<58){b=(b<<1)+(b<<3)+(ch^48),ch=getchar();}x=b;while(x>1)x/=10;x=f?-a-x:a+x;return 1;}inline void print(double x){if(x<0){putchar(45),x=-x;}x=round((long double)x*POW[precision])/POW[precision],print((long long)x),putchar(46),x-=(long long)(x);for(int i=1;i<=precision;i++)x*=10,putchar(x+48),x-=(int)x;}template<typename T,typename...T1>inline int read(T&a,T1&...other){return read(a)+read(other...);}template<typename T,typename...T1>inline void print(T a,T1...other){print(a),print(other...);}struct Fast_IO{~Fast_IO(){fwrite(obuf,p3-obuf,1,stdout);}}io;template<typename T>Fast_IO&operator>>(Fast_IO&io,T&b){return read(b),io;}template<typename T>Fast_IO&operator<<(Fast_IO&io,T b){return print(b),io;}
#define cout io
#define cin io
#define endl '\n'
}using namespace fast_IO;
const int maxn = 2e6 + 10, mod = 1e9 + 7;
const int maxm = 1e5 + 10;
int N, M;
string S[maxm];
unordered_map<int, int> mp1, mp2;
int cnt, pw1[maxm], pw2[maxm];
//int inpw1[maxn], inpw2[maxn];
const int base1 = 97, base2 = 131;
vector<int> g[maxn];
const int mod1 = 1e9 + 7, mod2 = 998244853;
int qmi(int a, int b, int P) {
	int res = 1;
	while (b) {
		if (b & 1) {
			res = 1ll * res * a % P;
		}
		a = 1ll * a * a % P;
		b >>= 1;
	}
	return res;
}
vector<int> s1[maxm], s2[maxm];
int sub1 (int id, int l, int r) {
	if (l == 0) {
		return s1[id][r];
	}
	return (s1[id][r] - 1ll * s1[id][l - 1] * pw1[r - l + 1] % mod1 + mod1) % mod1;
}
int sub2 (int id, int l, int r) {
	if (l == 0) {
		return s2[id][r];
	} 
	return (s2[id][r] - 1ll * s2[id][l - 1] * pw2[r - l + 1] % mod2 + mod2) % mod2;
} 

void solve() {
	cin >> N >> M;
	pw1[0] = pw2[0] = 1;
	for (int i = 1; i < maxm; i ++ ) {
		pw1[i] = 1ll * pw1[i - 1] * base1 % mod1;
		pw2[i] = 1ll * pw2[i - 1] * base2 % mod2;
	}
//	inpw1[maxm - 1] = qmi(pw1[maxm - 1], mod1 - 2, mod1);
//	inpw2[maxm - 1] = qmi(pw2[maxm - 1], mod2 - 2, mod2);
//	for (int i = maxm - 2; i >= 0; i -- ) {
//		inpw1[i] = 1ll * inpw1[i + 1] * base1 % mod1; 
//		inpw2[i] = 1ll * inpw2[i + 1] * base2 % mod2;
//	}
//	inpw1[0] = inpw2[0] = 1;
	cnt = 0;
	int mx = 0;
	for (int i = 1; i <= N; i ++ ) {
		cin >> S[i];
		mx = max (mx, (int)S[i].size());
	}
	S[N + 1] = "";
	for (int i = 1; i <= mx; i ++ )
		S[N + 1] += 'a';
	sort (S + 1, S + 1 + N + 1);
	for (int i = 1; i <= N; i ++ ) {
		int len = S[i].size();
		for (int j = 0; j < len; j ++ ) {
			if (j == 0) {
				s1[i].push_back((int)S[i][j]);
				s2[i].push_back((int)S[i][j]);
				continue;
			}
			int c1 = (1ll * s1[i][j - 1] * base1 + (int)S[i][j]) % mod1;
			int c2 = (1ll * s2[i][j - 1] * base2 + (int)S[i][j]) % mod2;
			s1[i].push_back(c1);
			s2[i].push_back(c2);
		}
	}
//	cout << "!fddssdf\n";
//	for (int i = 1; i <= N; i ++ ) {
//		for (int x : s1[i]) {
//			cout << x << ' ';
//		}
//		cout << '\n';
//	}
	// 知道50分部分分是什么了，应该是把每一个区间给搞出来之后莫队 nsqrtn
	for (int i = 1; i <= N; i ++ ) {
		// 对于每一个后缀存一下 
		string s = ""; int lens = S[i].size();
		for (int j = lens - 1; j >= 0; j -- ) {
			int w1 = sub1(i, j, lens - 1);
			int w2 = sub2(i, j, lens - 1);
			int s1 = mp1[w1];
//			if (i == 1 && j == lens - 1) {
//				cout << "fhdsifhsd\n";
//				cout << w1 << ' ' << w2 << ' ' << s1 << '\n';
//				cout << sub1(1, 3, 3) << ' ' << sub1(2, 2, 2) << '\n';
//			}
			if (!mp1[w1] || !mp2[w2]) {
				mp1[w1] = mp2[w2] = ++ cnt;
				s1 = cnt;
			}
			g[s1].push_back(i);
		}
	}
	for (int i = 1; i <= cnt; i ++ ) {
		g[i].push_back(N + 1);
	}
//	for (int i = 1; i <= cnt; i ++ ) {
//		cout << i << ":\n";
//		for (int x : g[i]) {
//			cout << x << ' ';
//		}
//		cout << '\n';
//	}
//	cout << "end1!\n";
//	for (int i = 1; i <= cnt; i ++ ) {
//		cout << i << ":\n";
//		for (int x : g[i]) {
//			cout << x << ' '; 
//		}
//		cout << '\n';
//	}
//cout << sub1(1, 0, 1) << '\n';
//cout << sub1(2, 0, 1) << '\n';
	while (M -- ) {
		string s, t;
		cin >> s >> t;
		int sum = 0;
		if (max((int)s.size(), (int)t.size()) > mx) {
			cout << "0\n";
			continue;
		}
		int l = 1, r = N + 1;
		while (l < r) {
			int mid = (l + r) >> 1;
			if (S[mid] < s)
				l = mid + 1;
			else
				r = mid;
		}
		int l1 = l, r1 = N + 1;
		int lens = s.size(); 
		string s2 = s.substr(0, lens - 1) + char(s[lens - 1] + 1);
		while (l1 < r1) {
			int mid = (l1 + r1) >> 1;
			if (S[mid] <= s2)
				l1 = mid + 1;
			else
				r1 = mid;
		}
		l1 -- ;
		//相当于需要的就是 l ~ l1 这个区间了
		if (l > l1) {
			cout << "0\n";
			continue;
		}
		for (int i = 0; i < (int)t.size(); i ++ ) {
			sum = 1ll * sum * base1 % mod1 + (int)t[i]; 
			sum %= mod1;
		}
		int id = mp1[sum];
//		cout << l << ' ' << l1 << ' ' << id <<  '\n';
//		for (int x : g[id]) {
//			cout << x << ' ';
//		}
//		cout << '\n';
		int low = lower_bound(g[id].begin(), g[id].end(), l) - g[id].begin();
		int upp = upper_bound(g[id].begin(), g[id].end(), l1) - g[id].begin() - 1;
		if (low > upp) {
			cout << "0\n";
			continue;
		}
//		cout << low << ' ' << upp << ' ' << id << '\n';
		cout << upp - low + 1 << '\n'; 
	}
	// 但是我这个复杂度真的对吗？ 
	// 我发现了，其实常数大的我这个做法也会似 
}

signed main() {
	// 极限数据我要跑 3s ！！！！ 
  int T = 1;
  while (T--)solve();
  return 0;
}
/*
8 7
GCGCUACCCCAACACAAGGCAAGAUAUA
G
GGAC
GCGG
U
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCCG
GCGCUGA
GCGCUACCC A
GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA
*/