Receiving a Fax

Fax data is compressed with run-length encoding (RLE). The encoded stream is a sequence of packets, and each packet begins with one control byte.

If the most significant bit of the control byte is 0, the packet is a literal packet. Add 1 to the value stored in the remaining 7 bits; that many bytes immediately follow the control byte and must be copied to the decoded output unchanged. A literal packet can therefore store from 1 to 128 bytes.

If the most significant bit of the control byte is 1, the packet is a run packet. Add 3 to the value stored in the remaining 7 bits; that is the number of times to repeat the next byte. A run packet can therefore represent from 3 to 130 copies of the same byte.

Decode each encoded byte stream and output the original bytes.

The first line contains the number of data sets P (1 <= P <= 1000).

Each data set begins with one integer B (1 <= B <= 5000), the number of encoded bytes. The following lines contain exactly B encoded bytes written in hexadecimal. Each full line contains 80 hexadecimal digits, and the last line for a data set may contain fewer.

Two hexadecimal digits represent one byte. Hexadecimal digits are 0 through 9 and A through F.

For each data set, print several lines.

First print the number of decoded bytes. Then print the decoded bytes as uppercase hexadecimal digits, with 80 hexadecimal digits per full line. The last line for a data set may contain fewer than 80 hexadecimal digits.