Kontakt for Two

Elk Valera loves playing Kontakt, a popular word game. Lately he rarely gets to play it, because the game needs at least three players, and gathering three people is hard with limited time and mismatched schedules.

So Valera invented a two-player version called Kontakt for Two. One player picks a non-empty word $S$ and reveals its first letter. The guesser names words that start with that letter, one after another, and the first player says whether each word is correct. The guesser may not repeat a word.

If the guesser names $K$ words, where $K$ is a fixed number, without guessing the word, the first player reveals the second letter. From then on, the guesser may name only words that start with these two letters and that they have not named before. This holds even when the guesser knew only one letter. If, after the second letter appears, the guesser can name another $K$ words, the first player reveals the third letter, and so on.

If the first player has revealed every letter and the guesser then names $K$ words starting with the word without naming it, the first player states that the revealed letters form the word, and the game ends. The game also ends when the guesser names the word.

To make the game more interesting, Valera, playing the first player, picks a word that makes the guesser make as many attempts as possible. A correct attempt also counts. The course of the game depends on the guesser's vocabulary and on the chosen $K$. Valera knows his friends well, so he can list every word each of them knows. He always picks a word the guesser knows. Choosing the word and $K$ is not easy.

Valera wants a program that, given a dictionary and $Q$ pairs of (secret word, $K$), finds the maximum number of words the guesser can name before the game ends.

The first line contains a single integer $N$, the number of words in the dictionary of the potential guesser. Each of the next $N$ lines contains one non-empty word of lowercase English letters. The total length of all words does not exceed $2 \cdot 10^5$.

Words may be identical in spelling. For example, in Russian, замОк and зАмок are different words with the same spelling, because the stress differs. In the language Valera's group plays in, many accent patterns exist, so identically spelled words can be common. During the game, players tell such words apart by how they pronounce them.

The line $N+2$ contains $Q$ ($1 \leq Q \leq 2 \cdot 10^5$), the number of queries. Each of the next $Q$ lines contains two integers $w$ and $k$ ($1 \leq w, k \leq N$): the index of the secret word in the dictionary and the value of $K$. Words are numbered from 1 in input order.

For each query, print on a separate line one integer: the maximum number of words the guesser can name before the game ends by a correct guess or by the first player revealing the word.