비밀번호 조정

또 다른 IPSC 대회가 막 시작되었는데 당신은 늦었습니다. PC로 달려갔지만 화면이 잠겨 있어서 잠금을 풀려면 비밀번호를 빨리 입력해야 합니다.

비밀번호 입력창은 다음 키만 지원합니다.

잘못된 비밀번호를 제출하면 오류 메시지가 나오고, 빈 새 입력창이 열린다.

비밀번호는 P이다. 급하게 입력하느라 문자열 Q를 입력창에 쳤다. Q는 P와 다를 수 있다. 오타가 한두 개 있을 수도 있고, 아예 다른 문자열일 수도 있다.

P와 Q가 주어졌을 때, 추가 키 입력을 가능한 한 적게 써서 로그인하라.

입력의 첫 줄에 테스트 케이스의 수 t가 주어진다. (t ≤ 1000) 각 테스트 케이스 앞에는 빈 줄이 하나 있다.

각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 올바른 비밀번호 P가, 둘째 줄에는 이미 입력한 문자열 Q가 주어진다. 두 문자열은 모두 비어 있지 않고, 길이는 50 이하이다.

각 테스트 케이스마다 누를 키의 순서를 한 줄에 출력한다. enter는 *, backspace는 <로 나타낸다.

최적해가 여러 개라면 그중 아무거나 출력해도 된다.

첫 번째 테스트 케이스에서는 오타를 지울 때까지 backspace를 계속 누른다. 두 번째 테스트 케이스에서는 곧바로 enter를 눌러 오류 메시지를 받은 뒤, 빈 입력창에서 새로 시작하는 편이 더 빠르다.