n, q = gets.split.map(&:to_i)
words = (1..n).map { gets.chomp }.sort
index1 = {}
(0..n-1).each do |i|
  index1[words[i]] = i
end
reversed = words.map(&:reverse).sort
index2 = {}
(0..n-1).each do |i|
  index2[reversed[i].reverse] = i
end

l = Math.sqrt(n).ceil
buckets = Array.new(l).map { Array.new(l).map { Array.new } }
words.each do |word|
  i = index1[word]
  j = index2[word]
  buckets[i / l][j / l] << [i, j]
end

q.times do
  prefix, suffix = gets.chomp.split(" ")
  suffix.reverse!
  i1 = (0..n-1).bsearch {|i| words[i] >= prefix }
  if i1 == nil or words[i1] !~ /^#{prefix}/
    puts 0
    next
  end
  prefix = prefix[0..-2] + (prefix[-1..-1].ord + 1).chr
  i2 = (i1..n-1).bsearch {|i| words[i] >= prefix }
  i2 = i2 ? i2 - 1 : n - 1
  j1 = (0..n-1).bsearch {|j| reversed[j] >= suffix }
  if j1 == nil or reversed[j1] !~ /^#{suffix}/
    puts 0
    next
  end
  suffix = suffix[0..-2] + (suffix[-1..-1].ord + 1).chr
  j2 = (j1..n-1).bsearch {|j| reversed[j] >= suffix }
  j2 = j2 ? j2 - 1 : n - 1
  answer = 0
  (i1/l..i2/l).each do |x|
    (j1/l..j2/l).each do |y|
      buckets[x][y].each do |u, v|
        answer += 1 if i1 <= u && u <= i2 && j1 <= v && v <= j2
      end
    end
  end
  p answer
end
