Cryptoquote

Interview

Time limit1sMemory limit128 MB

Summary

Decode each ciphertext message by substituting letters using a given 26-letter mapping while preserving spaces.

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

Problem

A Cryptoquote restores an encrypted message by replacing each uppercase letter in the ciphertext with another fixed uppercase letter.

For instance, if the ciphertext HPC PJVYMIY is restored as ACM CONTEST, then the conversion includes H -> A, P -> C, C -> M, J -> O, V -> N, Y -> T, M -> E, and I -> S. In other words, every letter that appears in the ciphertext must have a defined restored letter.

Given an encrypted message and a conversion rule, write a program that restores each message to its original form.

Input

The first line contains the number of test cases T. (1 <= T <= 1000)

Each test case consists of two lines. The first line contains an encrypted message of length at most 100, and the second line contains a conversion rule made of 26 uppercase letters. The first character of the rule is the letter to restore when A appears in the ciphertext, the second character is the letter to restore when B appears, ..., and the twenty-sixth character is the letter to restore when Z appears. No letter appears more than once in the conversion rule.

The encrypted message may contain spaces, and those spaces must remain in the restored message.

Output

For each test case, output the restored original message on its own line.

Examples1

Example 1

Input

2
HPC PJVYMIY
BLMRGJIASOPZEFDCKWYHUNXQTV
FDY GAI BG UKMY
KIMHOTSQYRLCUZPAGWJNBVDXEF

Expected output

ACM CONTEST
THE SKY IS BLUE