G. Странные запросы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Булата есть $$$n$$$ строк, и ему надо ответить на $$$q$$$ запросов. Каждый запрос состоит из двух строк $$$l_i$$$ и $$$r_i$$$. Для такого запроса ему нужно подсчитать количество строк из заданного набора таких, что либо $$$l_i$$$ является её префиксом, либо $$$r_i$$$ является её суффиксом, либо выполняются оба условия (таким образом, строка с префиксом $$$l_i$$$ и суффиксом $$$r_i$$$ одновременно считается один раз).

Помогите Булату ответить на запросы.

Входные данные

Первая строка содержит единственное целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$), количество строк. Далее даны сами $$$n$$$ строк (каждая дана в отдельной строке). Следующая строка содержит единственное целое число $$$q$$$ ($$$1 \leq q \leq 10^5$$$), количество запросов. Далее идут $$$q$$$ строк, описывающие запросы. $$$i$$$-я строка содержит $$$l_i$$$ и $$$r_i$$$ разделенные пробелом. Ни одна из строк во вводе не пуста.

Суммарная длина всех строк (включая запросы) не превышает $$$10^5$$$. Все строки состоят только из строчных букв английского алфавита.

Выходные данные

Для каждого из запросов в отдельной строке выведите по одному целому числу, количеству строк, содержащих либо необходимый префикс, либо суффикс, либо оба одновременно.

Пример
Входные данные
3
bat
eca
baca
1
ba ca
Выходные данные
3