둘이 하는 콘탁트

엘크 발레라는 널리 알려진 단어 게임인 콘탁트를 무척 좋아한다. 하지만 최근에는 이 게임을 자주 하지 못한다. 콘탁트는 최소 세 명이 참여해야 하는데, 시간이 부족하고 일정도 맞지 않아 세 명이 모이기가 어렵기 때문이다.

그래서 발레라는 둘이 하는 새로운 게임인 둘을 위한 콘탁트를 만들었다. 한 사람이 빈 문자열이 아닌 단어 $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$)가 주어진다. 다음 $Q$개 줄에는 각각 두 정수 $w$와 $k$ ($1 \leq w, k \leq N$)가 주어진다. $w$는 사전에 있는 출제 단어의 번호이고, $k$는 가정하는 $K$의 값이다. 단어는 입력 순서대로 1번부터 번호가 붙는다.

각 질문에 대해 한 줄에 정수 하나를 출력한다. 이 정수는 정답 맞히기나 출제자의 단어 공개로 게임이 끝나기 전까지 상대가 말할 수 있는 단어의 최대 개수이다.