믿을 수 없는 전령들

여섯 명의 전령이 메시지를 차례대로 전달한다. 각 전령은 다음 사람에게 넘기기 전에 항상 똑같은 방식으로 메시지를 조금씩 바꾸므로, 마지막으로 임금에게 도착한 메시지는 원래 메시지와 다르다.

메시지는 숫자(09)와 영문자(az, A~Z)로 이루어진 비어 있지 않은 문자열이며, 대문자와 소문자는 구별한다. 여섯 전령과 그 변환은 다음과 같다.

• J: 모든 문자를 왼쪽으로 한 칸씩 회전한다. 예를 들어 aB23d는 B23da가 된다.
• C: 모든 문자를 오른쪽으로 한 칸씩 회전한다. 예를 들어 aB23d는 daB23가 된다.
• E: 메시지의 왼쪽 절반과 오른쪽 절반을 맞바꾼다. 길이가 홀수이면 가운데 문자는 그대로 둔다. 예를 들어 e3ac는 ace3, aB23d는 3d2aB가 된다.
• A: 메시지를 뒤집는다. 예를 들어 aB23d는 d32Ba가 된다.
• P: 모든 숫자를 $1$씩 늘린다. 9는 0이 된다. 영문자는 바뀌지 않는다. 예를 들어 aB23d는 aB34d, e9ac는 e0ac가 된다.
• M: 모든 숫자를 $1$씩 줄인다. 0은 9가 된다. 영문자는 바뀌지 않는다. 예를 들어 aB23d는 aB12d, e0ac는 e9ac가 된다.

전령들이 메시지를 전달한 순서와 임금이 마지막으로 받은 메시지가 주어질 때, 원래 메시지를 복원하시오.

예를 들어 순서가 A, J, M, P이고 임금이 aB23d를 받았다고 하자. 원래 메시지에 이 순서대로 변환을 적용하면 다음과 같다.

• 원래 메시지: 32Bad
• A(뒤집기) 후: daB23
• J(왼쪽 회전) 후: aB23d
• M(숫자 감소) 후: aB12d
• P(숫자 증가) 후: aB23d (임금이 받은 메시지)

따라서 원래 메시지는 32Bad이다.

첫째 줄에 데이터 집합의 개수 $n$이 양의 정수로 주어진다. 각 데이터 집합은 두 줄로 주어진다.

• 전령들의 순서: 각 전령의 문자(J, C, E, A, P, M 중 하나)를 이어 쓴 문자열
• 임금이 마지막으로 받은 메시지

한 순서에 등장하는 전령의 수는 $1$ 이상 $6$ 이하이며, 같은 전령은 한 순서에 두 번 이상 나오지 않는다. 각 메시지의 길이는 $1$ 이상 $25$ 이하이다.

각 데이터 집합마다 복원한 원래 메시지를 한 줄에 출력한다.