Everyone knows that how much Shahjahan loved Mumtaaz, that he got built the Taj Mahal in the memory of his beloved Mumtaaz. Once Mumtaaz had fight with Shahjahan and she went to her father's home. Shahjahan then wrote a letter to Mumtaaz requesting her to come back, but then suddenly he realized that it is not safe to write letter in plain format (non-encoded message), so he thought whole day for a good method of encryption and then came up with a great idea of decoding his messages.

The technique of encoding messages used by Shahejahan is describes as-
1. A key K is set of digits (0-9) such that its value doesn't exceed 10⁶.
2. A message M is set of small letters (a-z) such that its length doesn't exceed 500.
3. The encoding function F(m, k) = m' is a function that takes one digit from key and one character from message and encode it to another character.

The encoding algorithm is given by following pseudo code-

start of code

1. Repeat until message has characters to be encoded.

2. Read next character c, of message.
3. Read next digit k, of key.
4. Encode using the function F(m, k) = m' : m' = m + k.

5. If last digit k, of key is read then start reading in reverse order.
6. If first digit k, of key is read while reading in reverse order, then start again reading in forward direction.

end of code

The addition operation to characters is cyclic. Consider the following examples demonstrating the operator-
1. 'a' + 2 = 'c'
2. 't' + 1 = 'u'
3. 'z' + 2 = 'b'
4. 'y' + 0 = 'y'

Consider the following encoding of message "mumtaaz" with key 132-

So message "mumtaaz" is encoded as "nxovdba"

Input

First line of input it T (T < 10001), total number of test cases.
Each test case is consist of two lines, the first line contains key and second line contains encoded message.

Output

For each test cases, output the original message in single line.

Example

Input:
6
132
nxovdba
212
uitktjvjmc
011
lfbejngafspsasfjnposubot
123
jnrygzpw
11
lfbejngafspsasfjnposubot
130
behipbobu


Output:
mumtaaz
shrishtika
leadingzerosareimportant
iloveyou
keadimfzerorzreimonrtans
abhimanyu