문자열 변환

어벤져스는 수많은 적들로부터 정보를 숨기기 위해 메시지를 암호화할 방법을 찾고 있습니다. 아이언맨은 다음과 같은 방법을 제안합니다.

여러 개의 문자열 변환 규칙이 주어집니다. 각 변환 규칙(생성 규칙)은 한 글자를 두 글자로 바꾸며, 현재 문자열에서 그 글자가 처음 나타나는 위치에만 적용됩니다. 해당 글자가 문자열에 없으면 문자열은 그대로 유지됩니다. 규칙을 적용해 새 문자열이 만들어지면 그 문자열이 다음 규칙의 대상이 되고, 남은 규칙이 없을 때까지 이 과정을 반복합니다.

각 단어는 서로 독립적인 대상 문자열로 취급하며, 모든 규칙을 주어진 순서대로 각 단어에 차례로 적용합니다.

예를 들어 규칙 A → OA를 문자열 CAT에 적용하면 COAT가 되고, 문자열 DATA에 적용하면 DOATA가 됩니다.

첫째 줄에는 테스트 케이스의 개수 $T$ ($T < 100$)가 주어집니다. 각 테스트 케이스는 두 줄로 이루어집니다.

• 첫째 줄에는 변환 규칙들이 lhs rhs 쌍의 나열로 주어집니다. lhs는 한 개의 대문자, rhs는 두 개의 대문자이며, 각 쌍은 공백으로 구분됩니다.
• 둘째 줄에는 변환할 단어들이 공백으로 구분되어 주어집니다.

모든 단어는 대문자로만 이루어져 있습니다.

각 테스트 케이스마다 한 줄을 출력합니다. 그 줄은 Transformed strings: 로 시작하고, 이어서 변환된 단어들을 원래 순서대로 출력하되 각 단어 뒤에 공백 하나를 붙입니다.