18106번 - <<Контакт>> для двоих 다국어

Лось Валера очень любит играть в <<Контакт>> --- широко популярную словесную игру; однако поиграть в нее в последнее время удается нечасто, ведь в игре должны участвовать не менее трех игроков, а собраться вместе как минимум втроем из-за нехватки времени и нестыкующихся графиков крайне затруднительно...

В силу этого, лось Валера придумал новую игру --- <<Контакт для двоих>>. Суть ее заключается в следующем. Один из игроков загадывает некоторое непустое слово $S$, которое второй игрок должен отгадать, и сообщает первую букву этого слова. Второй игрок, пытаясь угадать слово, называет одно за другим слова, начинающиеся на заданную букву, а первый игрок сообщает ему, верное ли слово, причем второй игрок не должен повторяться. Если второй игрок назвал  некоторое наперед заданное число $K$ слов и так и не угадал слово, то первый игрок сообщает вторую букву слова; после этого, второй игрок может называть лишь слова, начинающиеся с этих двух букв и не названные им ранее (в том числе и когда он знал лишь одну букву). Если после появления второй буквы, второй игрок сумеет назвать еще $K$ слов, то первый игрок сообщает третью букву, и т.д. Если в какой-то момент оказывается, что первый игрок уже назвал все буквы своего слова, а второй после этого назвал $K$ слов, начинающихся с него, но само слово не назвал, то первый игрок просто сообщает, что уже открытые буквы и образуют загаданное слово, и игра заканчивается.

Чтобы игра была интереснее, лось Валера, играя за первого игрока, старается загадать такое слово, чтобы второй игрок сделал как можно больше попыток угадать его (удачная попытка также считается). Однако сам процесс игры зависит от словарного запаса второго игрока, а также от выбранного числа $K$. Так как лось Валера хорошо знает своих друзей, то для каждого из них  Валера может выписать все слова, которые тот знает. Конечно же, чтобы не расстраивать второго игрока, Валера всегда загадывает слово, которое игрок знает. Однако, не так-то просто выбрать это слово и число $K$. Поэтому Валера решил написать программу, которая по заданному словарю и $Q$ парам <<загаданное слово -- значение $K$>> определяет, какое максимальное число слов может назвать второй игрок, пока игра не закончится угадыванием слова вторым игроком или сообщением слова первым.

Лось Валера справился с задачей. Справитесь ли вы?

В первой строке записано единственное целое положительное число $N$ --- количество слов в словаре потенциального второго игрока. В каждой из следующих $N$ строк записано одно  непустое слово этого словаря, состоящее из строчных букв английского алфавита. Суммарная длина слов не превосходит $2 \cdot 10^5$.

Обратите внимание: слова могут быть одинаковыми по написанию, например, потому, что они различаются при произношении ударениями: к примеру, в русском языке слова <<замОк>> и <<зАмок>> разные слова, хотя пишутся одинаково. В языке, на котором лось Валера и его друзья любят играть в <<Контакт>>, количество возможных акцентов, делающих одинаково записываемые слова разными по звучанию, очень велико. Во время игры участники полностью различают одинаково записываемые слова, произнося их по разному.

В $(n+2)$-й строке содержится целое число $Q$, ($1 \leq Q \leq 2 \cdot 10^5$) --- количество исследуемых пар <<загаданное слово -- значение $K$>>. В следующих $Q$ строках записаны по два целых числа $w$ и $k$ ($1 \leq w, k \leq n$) --- номер загаданного слова из словаря и предполагаемое значение $K$. Cлова нумеруются в том порядке, в котором они заданы выше, начиная с единицы.

Для каждой из $Q$ пар выведите в отдельное строке единственное целое число --- максимальное количество слов, которые может назвать второй игрок.