Unreliable Messengers

Interview

Time limit1sMemory limit128 MB

Summary

Given a sequence of reversible string transformations and the final message, undo each transformation in reverse order to recover the original message.

Level: Easy3 of 10
Topics: String, Simulation, Implementation
Solved: No attempts yet

Problem

Six messengers relay a message one after another. Each messenger always applies the same fixed change to the message before passing it on, so the message that finally reaches the King differs from the original.

A message is a non-empty string of digits (0-9) and letters (a-z, A-Z); uppercase and lowercase are distinct. The six messengers and their transformations are:

J rotates every character one position to the left. For example, aB23d becomes B23da.
C rotates every character one position to the right. For example, aB23d becomes daB23.
E swaps the left half of the message with the right half. If the length is odd, the middle character stays in place. For example, e3ac becomes ace3, and aB23d becomes 3d2aB.
A reverses the message. For example, aB23d becomes d32Ba.
P increases every digit by one; 9 becomes 0. Letters are unchanged. For example, aB23d becomes aB34d, and e9ac becomes e0ac.
M decreases every digit by one; 0 becomes 9. Letters are unchanged. For example, aB23d becomes aB12d, and e0ac becomes e9ac.

Given the order in which the messengers relayed the message and the message the King finally received, recover the original message.

For example, suppose the order is A, J, M, P and the King received aB23d. Applying the transformations to the original message in that order gives:

original message: 32Bad
after A (reverse): daB23
after J (rotate left): aB23d
after M (decrease digits): aB12d
after P (increase digits): aB23d (the message the King received)

So the original message is 32Bad.

Input

The first line contains a positive integer $n$ , the number of data sets. Each data set is given on two lines:

the order of the messengers, written as a string of their letters (each one of J, C, E, A, P, M);
the message the King finally received.

The number of messengers in an order is between $1$ and $6$ inclusive, and no messenger appears more than once in a single order. The length of each message is between $1$ and $25$ inclusive.

Output

For each data set, print the recovered original message on its own line.

Examples7

Example 1

Input

5
AJMP
aB23d
E
86AE
AM
6
JPEM
WaEaETC302Q
CP
rTurnAGundam1isdefferentf

Expected output

32Bad
AE86
7
EC302QTWaEa
TurnAGundam0isdefferentfr

Example 2
Input
```
1
J
abcd
```
Expected output
```
dabc
```
Example 3
Input
```
1
C
abcd
```
Expected output
```
bcda
```
Example 4
Input
```
1
E
abcde
```
Expected output
```
decab
```
Example 5
Input
```
1
A
abc
```
Expected output
```
cba
```
Example 6
Input
```
1
P
a0b9
```
Expected output
```
a9b8
```
Example 7
Input
```
1
M
a9b0
```
Expected output
```
a0b1
```