Unreliable Message

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem A: Unreliable Messengers

The King of a little Kingdom on a little island in the Pacific Ocean frequently has childish ideas. One day he said, gYou shall make use of a message relaying game when you inform me of something.h In response to the Kingfs statement, six servants were selected as messengers whose names were Mr. J, Miss C, Mr. E, Mr. A, Dr. P, and Mr. M. They had to relay a message to the next messenger until the message got to the King.

Messages addressed to the King consist of digits (e0f-e9f) and alphabet characters (eaf-ezf, eAf-eZf). Capital and small letters are distinguished in messages. For example, gke3E9Aah is a message.

Contrary to Kingfs expectations, he always received wrong messages, because each messenger changed messages a bit before passing them to the next messenger. Since it irritated the King, he told you who are the Minister of the Science and Technology Agency of the Kingdom, gWe donft want such a wrong message any more. You shall develop software to correct it!h In response to the Kingfs new statement, you analyzed the messengersf mistakes with all technologies in the Kingdom, and acquired the following features of mistakes of each messenger. A surprising point was that each messenger made the same mistake whenever relaying a message. The following facts were observed.

Mr. J rotates all characters of the message to the left by one. For example, he transforms gaB23dh to gB23dah.

Miss C rotates all characters of the message to the right by one. For example, she transforms gaB23dh to gdaB23h.

Mr. E swaps the left half of the message with the right half. If the message has an odd number of characters, the middle one does not move. For example, he transforms ge3ach to gace3h, and gaB23dh to g3d2aBh.

Mr. A reverses the message. For example, he transforms gaB23dh to gd32Bah.

Dr. P increments by one all the digits in the message. If a digit is e9f, it becomes e0f. The alphabet characters do not change. For example, he transforms gaB23dh to gaB34dh, and ge9ach to ge0ach.

Mr. M decrements by one all the digits in the message. If a digit is e0f, it becomes e9f. The alphabet characters do not change. For example, he transforms gaB23dh to gaB12dh, and ge0ach to ge9ach.

The software you must develop is to infer the original message from the final message, given the order of the messengers. For example, if the order of the messengers is A -> J -> M -> P and the message given to the King is gaB23dh, what is the original message? According to the features of the messengersf mistakes, the sequence leading to the final message is

         A           J           M           P
g32Badh --> gdaB23h --> gaB23dh --> gaB12dh --> gaB23dh.

As a result, the original message should be g32Badh.

Input

The input format is as follows.


     n
     The order of messengers
     The message given to the King
                .
                .
                .
     The order of messengers
     The message given to the King

The first line of the input contains a positive integer n, which denotes the number of data sets. Each data set is a pair of the order of messengers and the message given to the King. The number of messengers relaying a message is between 1 and 6 inclusive. The same person may not appear more than once in the order of messengers. The length of a message is between 1 and 25 inclusive.

Output

The inferred messages are printed each on a separate line.

Sample Input

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

Output for the Sample Input

32Bad
AE86
7
EC302QTWaEa
TurnAGundam0isdefferentfr

Source: ACM International Collegiate Programming Contest , Asia Regional Aizu, Aizu, Japan, 2003-11-02
http://web-ext.u-aizu.ac.jp/conference/ACM/