Once upon a time chef decided to learn encodings. And, obviously, he started with the easiest one (well, actually the easiest after Caesar cypher) – substitution cypher.
But very soon Chef got bored with encoding/decoding, so he started thinking how to hack this cypher.
He already knows some algorithm, which is not always correct,
but it’s sufficient for now. Here is its description.
Imagine we know frequency sequence of English letters (this means, that letters are sorted by their frequency of appearing in English texts, in ascending order).
And let’s find frequency sequence of cyphered letters (if some of them appear equal number of times, then first in frequency sequence will be lower letter between them).
Now, using this two frequency sequences we can recover plain text. Just substitute cyphered letter with origin one, if they are at same positions in sequences.
Now, Chef has frequency sequence of English letters and cypher text. And he asks you to recover plain text. Please, help him.

Input
In first line number T is given - number of test cases. Then T test cases follow. Each test case consists of two lines - frequency sequence and encrypted text.

Output
For each test case you should output decrypted with the given frequency sequence text. Please note, that the case of letters should be preserved.

Constraints

1 ≤ T ≤ 1000;
Length of frequency sequence is always 26;
1 ≤ length of the text ≤ 150000;
1 ≤ sum lengths of all texts ≤ 150000.
Frequency sequence consists of all lowercase English letters. Text consists of any characters.

Example

Input:
3
qwrtyuipasdfgjkzxcvbnmheol
dummy!
bfgjklmopqrstuwxzhvnicdyea
abcd b efgd hbi!
qwrtyuipasdfgjkzxcvbnmheol
Dummy!

Output:
hello!
have a nice day!
Hello!

见题面

见题面