Steganography is a method of cryptography where a message or entire document can be hidden inside of another file or image which shows no evidence that there is data hidden in it. Typically, the message or document to be sent is first encrypted and compressed, and then combined with an existing file in the bits that are less significant.

Hemant Verma is a secret agent who wants to send some classified information to his head office , the amount of data is very large , he needs your help to encode the message into image . You will be given an "image" and you will encode a given message into it and return the new image. The returned image should be in the same format as the original image.

The image will be in the format of a string of various lines where each three digits represent a number from 0 to 255, inclusive (leading zeros will be added as necessary), which is a pixel value in the image. You will also be given a  message which contains the message you would like to encode into the image.

You will first encode the message into numbers representing the characters in the message - spaces will be 0, 'A'-'Z' will be 1-26, 'a'-'z' will be 27-52, '0'-'9' will be 53-62, and 63 will be used for any space after the message. All these numbers can be represented in binary with 6 digits. You will put each pair of bits (representing a number between 0 and 3) into the lowest two bits of the values in the image. For each character, you will put in the lowest two bits, then the middle two, then the highest two, and then continue to the next character. You will put them in the lowest two bits of the first pixel on the first row, then the second pixel on the first row, and so on until you get to the end of the first row, then the first pixel on the second row, and so on. Once you are out of characters, continue substituting the lowest two bits of each pixel value as if the current character were represented by number 63.

Input

First line contain T representing number of test case , for each test case first line contain message  then follow N the number of lines for image then following N line contain image.

0 < Length(message) < 1000
0 < T, N < 10000

Output

For each test case output the image in same format as input.

Example

Input:
2
hi
1
255123212001201222
hi
2
255123212
001201222

Output:
254120214003200222
254120214
003200222