SNGMSG - Encode Message

no tags 

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 106.
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-

Character c Digit k F(c, k)
m1n
u3x
m2o
t2v
a3d
a1b
z1a

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

hide comments
sk128: 2021-07-23 22:25:32

Do run this test case hue hue :)

5
9821
bpcikcpjw
5221
fcuijs
24
pelk
32510
ucreibbfb
0751
tofb

kumar_anubhav: 2020-06-06 11:28:46

AC in one go!!! nice problem Edge case to be take care of :)

shaakal: 2019-05-21 06:47:11

leading zeros are important

mag1x_: 2018-06-22 17:36:24

take key as string and then its all playing with string :)

venkat016: 2018-01-09 21:31:48

I got TLE please help @ajayc1007 and @priorityprasad_235

nadstratosfer: 2017-09-25 05:11:01

Inconsistent use of newlines in input. Use rstrip() in Python else WA.

yasho1: 2017-06-20 18:57:29

If the number of inputs given to the program is lesser than the number of test cases then how does the online judge evaluate the output??

sachinsharma12: 2017-01-24 12:59:50

Nyc problem)),,
Little thinking

cs_abhi2000: 2017-01-23 17:51:37

Nice program...
AC in one go :)

rajat_kumar: 2016-09-30 14:56:24

a great encoding algo ;)


Added by:AvmnuSng
Date:2014-02-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Abhimanyu Singh
My Problems