단어 인코딩

어떤 언어에서든 특정한 글자 조합은 절대 나타나지 않거나, 거의 나타나지 않아 존재하지 않는다고 볼 수 있습니다. 예를 들어 영어 단어 중에는 부분 문자열로 buv를 포함하는 것이 없습니다.

나타날 수 없는 글자 조합의 목록이 주어지면, 그 언어에서 가능한 "단어"의 수는 크게 줄어듭니다. 여기서 "단어"란 주어진 금지 조합 중 어느 것도 부분 문자열로 포함하지 않는, 소문자로만 이루어진 임의의 문자열을 뜻합니다.

모든 유효한 단어를 길이가 짧은 순서로, 길이가 같으면 사전순으로 나열하고 1번부터 번호를 매깁니다.

예를 들어 금지 조합이 q, ab, aaa뿐이라면 단어에는 다음과 같이 번호가 매겨집니다.

1.   a
2.   b
...
16.  p
17.  r
...
26.  aa
27.  ac
...
649. zz
650. aac

금지 조합 목록이 주어질 때, 주어진 단어에 대해서는 그 번호를, 주어진 번호에 대해서는 그 단어를 출력하는 프로그램을 작성하세요.

모든 단어의 길이는 최대 20자이며, 입력과 출력에 등장하는 어떤 번호도 2,000,000,000을 넘지 않습니다. 알파벳은 항상 소문자 a부터 z까지입니다.

첫째 줄에 테스트 케이스의 수 $T$가 주어집니다.

각 테스트 케이스의 첫째 줄에는 두 정수 $N$과 $M$이 주어집니다. $N$은 금지 조합의 개수 ($0 \le N \le 1000$), $M$은 질의의 개수 ($1 \le M \le 100$)입니다.

이어지는 $N$개의 줄에는 각각 길이가 1 이상 3 이하인 소문자 금지 조합이 하나씩 주어집니다.

그 다음 $M$개의 줄에는 각각 질의가 하나씩 주어지며, 양의 정수이거나 소문자 단어입니다. 단어 질의는 해당 테스트 케이스의 어떤 금지 조합도 포함하지 않으며, 번호 질의는 유효한 단어의 총 개수를 넘지 않습니다.

각 질의마다 한 줄에 답을 출력합니다. 단어가 주어지면 그 번호를, 번호가 주어지면 그 단어를 출력합니다.