import scala.annotation.tailrec
import scala.collection.mutable
object Main extends App {
  import scala.io.StdIn._

  val Array(n, q) = readLine.trim.split(' ').map(_.toInt)
  val prefix = Array.tabulate(n){ _ ⇒ readLine.trim}.sorted
  val (suffix, suffixToPrefix: SegArray) = prefix.map(_.reverse).zipWithIndex.sortBy(_._1).let(a ⇒ (a.map(_._1), SegArray(a.map(_._2))))

  for (_ ← 0 until q){
    val Array(pre, suf) = readLine.trim.split(' ').let{case Array(p, s) ⇒ Array(p, s.reverse)}
    val lower = lowerBound(prefix, pre)
    val upper = lowerBound(prefix, pre.next) - 1
    val from = lowerBound(suffix, suf)
    val until = lowerBound(suffix, suf.next)
    println(
      suffixToPrefix.count(from, until, lower, upper)
    )
  }

  def lowerBound(array: Array[String], target: String): Int = {
    var left = 0
    var right = array.length
    while(left < right){
      val mid = (left + right) / 2
      if (array(mid) < target){
        left = mid + 1
      }else {
        right = mid
      }
    }
    right
  }
  implicit class Lexical(val word: String) extends AnyVal {
    def next: String = {
      word.updated(word.length - 1, (word.last + 1).toChar)
    }
  }
  object Trie {
    def apply(words: Array[String]): Trie = {
      val root = new TrieImpl
      for ((word, index) ← words.zipWithIndex) {
        var trie = root
        trie.insert(index)
        for (position ← word.indices){
          trie = trie.findChildOrMake(word(position))
          trie.insert(index)
        }
      }
      root
    }
    private class TrieImpl extends Trie {
      private val child: mutable.Map[Char, TrieImpl] = mutable.Map[Char, TrieImpl]()
      private var min: Int = Int.MaxValue
      private var max: Int = Int.MinValue
      def insert(index: Int): Unit = {
        min = math.min(min, index)
        max = math.max(max, index)
      }
      def findChildOrMake(char: Char): TrieImpl = {
        child.get(char) match {
          case None ⇒
            val t = new TrieImpl
            child(char) = t
            t
          case Some(t) ⇒ t
        }
      }
      def findRange(prefix: String): Option[(Int, Int)] = {
        val (from, to) = TrieImpl.findRange(this, prefix, 0)
        if (to >= 0) Some(from, to)
        else None
      }
    }
    private object TrieImpl {
      @tailrec
      def findRange(trieImpl: TrieImpl, prefix: String, position: Int): (Int, Int) = {
        if (prefix.length == position) (trieImpl.min, trieImpl.max)
        else if (trieImpl.child.contains(prefix(position))){
          findRange(trieImpl.child(prefix(position)), prefix, position + 1)
        }else (0, -1)
      }
    }
  }
  trait Trie {
    def findRange(prefix: String): Option[(Int, Int)]
  }
  object SegArray{
    def apply(array: Array[Int]): SegArray = {
      makeSegArray(array, 0, array.length)
    }
    private[this] def makeSegArray(array: Array[Int], from: Int, until: Int): SegArray = {
      if (until - from <= 16) new Leaf(from, until, (from until until).map(array).toArray)
      else new Node(from, until, (from until until).map(array).sorted.toArray, makeSegArray(array, from, (from + until) / 2), makeSegArray(array ,(from + until) / 2, until))
    }

    private class Leaf (private[this] val mFrom: Int, private[this] val mUntil: Int, private[this] val mArray: Array[Int]) extends SegArray {
      override def count(from: Int, until: Int, lower: Int, upper: Int): Int = {
        (math.max(mFrom, from) until math.min(mUntil, until)).count(i ⇒ lower <= mArray(i - mFrom) && mArray(i - mFrom) <= upper)
      }
    }
    private class Node (private[this] val mFrom: Int, private[this] val mUntil: Int, private[this] val mSortedArray: Array[Int], private[this] val left: SegArray, private[this] val right: SegArray) extends SegArray {
      override def count(from: Int, until: Int, lower: Int, upper: Int): Int = {
        if (from <= mFrom && mUntil <= until) {
          upperBound(upper) - lowerBound(lower)
        }else if (until <= mFrom || mUntil <= from) {
          0
        }else {
          left.count(from, until, lower, upper) + right.count(from, until, lower, upper)
        }
      }
      private[this] def upperBound(target: Int): Int = {
        var left = 0
        var right = mSortedArray.length
        while(left < right){
          val mid = (left + right) / 2
          if (mSortedArray(mid) <= target){
            left = mid + 1
          }else {
            right = mid
          }
        }
        right
      }
      private[this] def lowerBound(target: Int): Int = {
        var left = 0
        var right = mSortedArray.length
        while(left < right){
          val mid = (left + right) / 2
          if (mSortedArray(mid) < target){
            left = mid + 1
          }else {
            right = mid
          }
        }
        right
      }
    }
  }
  sealed trait SegArray{
    def count(from: Int, until: Int, lower: Int, upper: Int): Int
  }
  implicit class Scope[T](val value: T) extends AnyVal {
    @inline
    def let[A](func: T ⇒ A): A = func(value)
  }
}


Measured memory_bytes: 478720