Sascha

사샤는 세 살 아이로, 어떤 단어 안의 일부 글자를 더 발음하기 쉬운 다른 글자로 바꾸어 말한다. 같은 글자라도 위치에 따라 그대로 말할 수도 있고 다른 글자로 바꿀 수도 있으므로, 바뀜 규칙이 단어 전체에 일관되게 적용된다고 볼 수는 없다.

사전에는 올바른 단어들이 주어진다. 사샤가 말한 단어와 같은 길이를 가진 사전 단어 중, 그 단어를 사샤가 말한 단어로 바꾸기 위해 필요한 위치별 글자 치환 횟수가 가장 적은 단어를 찾아라. 한 번의 치환은 한 위치의 글자를 다른 글자로 바꾸는 것이다.

가능한 단어가 여러 개이면 사전에 더 먼저 나온 단어가 더 그럴듯하다고 본다.

첫 줄에는 테스트 케이스의 수 n이 주어진다. (0 < n <= 10000)

각 테스트 케이스는 다음 순서로 주어진다.

• 사샤가 발음한 단어 한 줄
• 사전에 들어 있는 단어 수 w 한 줄 (0 < w <= 10000)
• 사전 단어 w개, 한 줄에 하나씩

모든 단어는 영어 소문자로만 이루어져 있으며 길이는 128자를 넘지 않는다. 한 테스트 케이스 안의 모든 사전 단어는 사샤가 발음한 단어와 길이가 같다.

각 테스트 케이스마다 사샤가 원래 말하려 했을 가능성이 가장 높은 단어를 한 줄에 출력한다. 가능한 단어가 여러 개이면 입력에서 더 먼저 나온 사전 단어를 출력한다.