#include <bits/stdc++.h>
using namespace std;
using psi = pair<string, int>;

template <typename T>
class merge_tree {
	const int n;
	vector<vector<T>> data;
	int size(int x) {
		int res;
		for (res = 1; res < x; res <<= 1);
		return res;
	}
	int query(int node, T val) {
		return lower_bound(data[node].begin(), data[node].end(), val) - data[node].begin();
	}
public:
	merge_tree(const vector<T>& data_) : n(size(data_.size())), data(n * 2) {
		for (int i = 0; i < (int)data_.size(); i++)
			data[i + n].push_back(data_[i]);
		for (int i = n - 1; i >= 0; i--)
			merge(data[i * 2].begin(), data[i * 2].end(), data[i * 2 + 1].begin(), data[i * 2 + 1].end(), back_inserter(data[i]));
	}
	int find(int l, int r, T val) {
		l += n; r += n;
		int res = 0;
		while (l < r) {
			if (l & 1) res += query(l++, val);
			if (r & 1) res += query(--r, val);
			l >>= 1; r >>= 1;
		}
		return res;
	}
};

int main()
{
	int N, Q;
	cin >> N >> Q;
	vector<psi> ss;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		ss.emplace_back(s, i);
	}
	auto rs = ss;
	for (int i = 0; i < N; i++) {
		reverse(rs[i].first.begin(), rs[i].first.end());
	}
	sort(ss.begin(), ss.end());
	sort(rs.begin(), rs.end());
	vector<int> pos1(N), pos2(N);
	for (int i = 0; i < N; i++) {
		pos1[ss[i].second] = i;
		pos2[rs[i].second] = i;
	}
	vector<int> data(N);
	for (int i = 0; i < N; i++) {
		data[i] = pos2[ss[i].second];
	}
	merge_tree<int> mt(data);
	while (Q--) {
		string pre, suf;
		cin >> pre >> suf;
		int l1, r1, l2, r2;
		{
			int lb = -1, ub = N;
			while (ub - lb > 1) {
				int c = (lb + ub) >> 1;
				if (ss[c].first.compare(0, pre.length(), pre) < 0) {
					lb = c;
				}
				else {
					ub = c;
				}
			}
			l1 = ub;
			lb = -1, ub = N;
			while (ub - lb > 1) {
				int c = (lb + ub) >> 1;
				if (ss[c].first.compare(0, pre.length(), pre) <= 0) {
					lb = c;
				}
				else {
					ub = c;
				}
			}
			r1 = ub;
		}
		reverse(suf.begin(), suf.end());
		{
			int lb = -1, ub = N;
			while (ub - lb > 1) {
				int c = (lb + ub) >> 1;
				if (rs[c].first.compare(0, suf.length(), suf) < 0) {
					lb = c;
				}
				else {
					ub = c;
				}
			}
			l2 = ub;
			lb = -1, ub = N;
			while (ub - lb > 1) {
				int c = (lb + ub) >> 1;
				if (rs[c].first.compare(0, suf.length(), suf) <= 0) {
					lb = c;
				}
				else {
					ub = c;
				}
			}
			r2 = ub;
		}
		printf("%d\n", mt.find(l1, r1, r2) - mt.find(l1, r1, l2));
	}
	return 0;
}

