Prefix Codes

Sam has found an ancient communication channel to the outside world. The channel is very slow, so Sam and his friends want to compress their messages so they can be sent faster. After much thought, Sam decides to use a binary prefix code.

A prefix code is a variable-length code in which no codeword is a prefix of any other codeword. For example, {a=0, b=10, c=11} is a prefix code, but {a=0, b=10, c=01} is not, because 0 is a prefix of 01.

A binary prefix code (codewords made of 0s and 1s) can be represented as a binary tree in which the symbols are the leaves and the path from the root to a leaf spells out that symbol's codeword. For simplicity, assume that moving to the left child appends a 0 and moving to the right child appends a 1. For example, the prefix codes {a=0, b=10, c=11} and {a=000, b=001, c=01, d=10, e=110, f=111} can be drawn as the following binary trees.

A binary tree can also be written compactly as a string. View a string of length $N$ as characters at positions $0$ through $N-1$. The root is at position $0$, and the left and right children of the node at position $k$ are at positions $2k+1$ and $2k+2$, respectively. Under this rule, the two trees above are written as the strings *a***bc and ****cd*ab****ef, where * marks an interior (non-leaf) or missing node.

To decode a compressed message, start at the root and move to the left or right child depending on whether the next bit is 0 or 1. When a leaf is reached, output its symbol and continue decoding the rest of the message starting again from the root.

Given a prefix code in string form together with several binary messages, decode each message back to its original text.

The first line contains the number of test cases $T$ ($T < 100$). Each of the following lines describes one test case: it begins with $k$, the number of messages to decode, followed by the string representation of the prefix code, and then the $k$ binary messages to decode. Every message is guaranteed to consist only of symbols that appear in the given prefix code.

For each test case, print one line containing the decoded messages, separated by single spaces.