Fax

A fax machine compresses data with run-length encoding (RLE). The data can be viewed as a sequence of byte values, and a maximal consecutive block of equal values is called a run. Instead of storing the whole sequence directly, RLE represents a run by storing one data value and the number of times it is repeated. This is useful for data with many runs, such as icons, text, and simple line graphics. For data with few runs, such as photographs, the encoded result may even be larger than the original.

You must encode one block of data using the RLE algorithm. One run is represented by 2 bytes. The first byte stores the repetition count, and the second byte stores the repeated value. In the count byte, the most significant bit is 1, and the remaining 7 bits store count - 3. Therefore one 2-byte run representation can encode 3 through 130 repetitions of the same value. The minimum run length is 3.

Bytes that are not part of a run are encoded by a prefix byte followed by the original bytes. The most significant bit of the prefix byte is always 0, and the value stored in it is the number of following non-run bytes minus 1. Thus one prefix byte can represent from 1 through 128 non-run bytes.

If a run is longer than 130 bytes, split it into several 2-byte run representations. Starting from the front, encode as many length-130 runs as possible. Any block of at least 3 equal values must be encoded as a run. If a non-run block is longer than 128 bytes, represent it with multiple prefix bytes. For example, a run of length 262 is encoded as two length-130 runs followed by a non-run block of length 2.

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

For each data set, the first line contains a decimal integer B (1 <= B <= 5000), the number of bytes.

The data to encode follows. Every data line except the last contains 80 hexadecimal characters, and the last line may contain fewer than 80. Two hexadecimal characters represent one byte. Each hexadecimal character is one of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

For each data set, first output the number of encoded bytes on its own line. Then output the encoded data in hexadecimal. Every output line except the last must contain 80 hexadecimal characters, and the last line must contain at most 80.