#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int INF = 1 << 30;

struct SuccinctIndexableDictionary {
  size_t length;
  size_t blocks;
  vector< unsigned > bit, sum;

  SuccinctIndexableDictionary() {
  }

  SuccinctIndexableDictionary(size_t _length) {
    length = _length;
    blocks = (length + 31) >> 5;
    bit.assign(blocks, 0U);
    sum.assign(blocks, 0U);
  }

  void set(int k) {
    bit[k >> 5] |= 1U << (k & 31);
  }

  void build() {
    sum[0] = 0U;
    for(int i = 1; i < blocks; i++) {
      sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);
    }
  }

  bool operator[](int k) const {
    return (bool((bit[k >> 5] >> (k & 31)) & 1));
  }

  int rank(int k) {
    return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));
  }

  int rank(bool val, int k) {
    return (val ? rank(k) : k - rank(k));
  }

  int select(bool val, int k) {
    if(k < 0 || rank(val, length) <= k) return (-1);
    int low = 0, high = length;
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if(rank(val, mid) >= k + 1) high = mid;
      else low = mid;
    }
    return (high - 1);
  }

  int select(bool val, int i, int l) {
    return select(val, i + rank(val, l));
  }
};

template< class T, int MAXLOG >
struct WaveletMatrix {
  size_t length;
  SuccinctIndexableDictionary matrix[MAXLOG];
  int zs[MAXLOG];
  int buff1[MAXLOG], buff2[MAXLOG];

  int freq_dfs(int d, int l, int r, T val, T a, T b) {
    if(l == r) return 0;
    if(d == MAXLOG) return (a <= val && val < b) ? r - l : 0;
    T nv = 1ULL << (MAXLOG - d - 1) | val, nnv = ((1ULL << (MAXLOG - d - 1)) - 1) | nv;
    if(nnv < a || b <= val) return 0;
    if(a <= val && nnv < b) return r - l;
    int lc = matrix[d].rank(1, l), rc = matrix[d].rank(1, r);
    return freq_dfs(d + 1, l - lc, r - rc, val, a, b) +
           freq_dfs(d + 1, lc + zs[d], rc + zs[d], nv, a, b);
  }

  WaveletMatrix(vector< T > data) {
    length = data.size();
    vector< T > l(length), r(length);
    for(int depth = 0; depth < MAXLOG; depth++) {
      matrix[depth] = SuccinctIndexableDictionary(length + 1);
      int left = 0, right = 0;
      for(int i = 0; i < length; i++) {
        bool k = (data[i] >> (MAXLOG - depth - 1)) & 1;
        if(k) r[right++] = data[i], matrix[depth].set(i);
        else l[left++] = data[i];
      }
      zs[depth] = left;
      matrix[depth].build();
      swap(l, data);
      for(int i = 0; i < right; i++) data[left + i] = r[i];
    }
  }

  int rangefreq(int left, int right, T lower, T upper) {
    return (freq_dfs(0, left, right, 0, lower, upper));
  }
};
// おれたちのウェーブレット行列


// おれたちの接尾辞配列はありませんでした

int N, Q;
pair< string, int > w[100000];
pair< string, int > t[100000];


int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> N >> Q;
  for(int i = 0; i < N; i++) {
    cin >> w[i].first;
    w[i].second = i;
    t[i] = w[i];
    reverse(begin(t[i].first), end(t[i].first));
  }
  sort(w, w + N);
  sort(t, t + N);

  vector< int > rev1(N), rev2(N);
  for(int i = 0; i < N; i++) rev1[w[i].second] = i;
  for(int i = 0; i < N; i++) rev2[t[i].second] = i;

  vector< pair< int, int > > pos;
  for(int i = 0; i < N; i++) {
    pos.emplace_back(rev1[i], rev2[i]);
  }
  sort(begin(pos), end(pos));
  vector< int > add(N), add2(N);
  for(int i = 0; i < N; i++) {
    add[i] = pos[i].second;
    add2[i] = pos[i].first;
  }
  WaveletMatrix< int, 23 > mat(add);
  while(Q--) {
    string x, y;
    cin >> x >> y;
    reverse(begin(y), end(y));
    auto x1 = lower_bound(w, w + N, make_pair(x, -1)) - w;
    x.back()++;
    auto x2 = lower_bound(w, w + N, make_pair(x, -1)) - w;
    auto y1 = lower_bound(t, t + N, make_pair(y, -1)) - t;
    y.back()++;
    auto y2 = lower_bound(t, t + N, make_pair(y, -1)) - t;
    cout << mat.rangefreq(x1, x2, y1, y2) << endl;
  }
}



Measured memory_bytes: 22664