QR

QR-коды (самый маленький из которых, размером $21$ пиксель на $21$ пиксель, показан ниже) представляют собой квадратные массивы черных или белых пикселей (модулей). Они содержат шаблоны обнаружения позиции (квадратные узоры "бычий глаз"), шаблоны синхронизации (чередующиеся черные и белые линии), шаблоны выравнивания в более крупных QR-кодах, информацию о формате (штриховые пиксели), информацию о версии в более крупных QR-кодах, а также кодовые слова данных и исправления ошибок (серые блоки по 8 пикселей).

QR-код размером $21$ на $21$ имеет $26$ кодовых слов данных и исправления ошибок. На самом низком уровне исправления ошибок для этого кода $19$ являются кодовыми словами данных и 7 — кодовыми словами исправления ошибок. Данные могут быть закодированы как числовые с $3$ числами на $10$ бит, как алфавитно-цифровые с $2$ символами на 11 бит, как байты по 8 бит или как кандзи с $13$ битами на символ. Данные кодируются в группах: режим, количество символов, биты данных символов. Режим может изменяться в потоке данных. Режим указывается 4-битным кодом, а количество символов — переменным количеством бит в зависимости от режима и размера QR-кода. Для кода $21$ на $21$ количество бит символов:

Весь поток данных заканчивается кодом завершения, который может быть усечен, если недостаточно места. Любое частично заполненное кодовое слово после кода завершения заполняется битами 0. Любые оставшиеся кодовые слова устанавливаются в 11101100, за которыми следуют чередующиеся 00010001. Числовые строки кодируются по 3 цифры за раз. Если остаются цифры, 2 цифры кодируются в 7 бит или 1 цифра в 4 бита. Например:

12345678 -> 123 456 78 -> 0001111011 0111001000 1001110

Префикс с режимом (0001) и количеством (8 -> 0000001000) составляет (4 + 10 + 10 + 10 +7) бит:

0001 0000001000 0001111011 0111001000 1001110

Алфавитно-цифровые строки кодируют символы (представляет символ пробела):

0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ$%*+-./:

как числа от 0 до 44, затем два символа кодируются в 11 бит:

* 45 +

если количество символов нечетное, последний символ кодируется в 6 бит. Например:

AC-42 -> (10,12,41,4,2) -> 10*45+12=462, 41*45+4=1849, 2->00111001110 11100111001 000010

Префикс с режимом и количеством составляет (4 + 9 + 11 + 11+ 6) бит:

0010 000000101 00111001110 11100111001 000010

8-битный двоичный и режим кандзи будут простыми для целей этой задачи. Коды кандзи будут просто непрозрачными 13-битными кодами; вам не нужно декодировать символы, которые они представляют, только шестнадцатеричные значения. Например:

8 бит 0x45 0x92 0xa3 -> 01000101 10010010 10100011

Префикс с режимом и количеством составляет (4 + 8 + 8 + 8 + 8) бит:

0100 00000011 01000101 10010010 10100011

Кандзи 0x1ABC 07x0345 -> 1101010111100 0001101000101

Префикс с режимом и количеством составляет (4 + 8 + 13 + 13) бит:

1000 00000010 1101010111100 0001101000101

Чтобы проиллюстрировать формирование содержимого из 19 кодовых слов QR-кода, объедините первые 3 последовательности выше (для числовых, алфавитно-цифровых и байтов). Конкатенируйте биты, разделите на 8-битные кодовые слова, добавьте кодовое слово завершения, любые заполняющие биты и заполняющие байты (41 + 41 + 36 бит данных + 4-битное кодовое слово завершения = 122 -> требуется 6 заполняющих бит, чтобы получить 16 байт, и чтобы заполнить 19 байт, требуется 3 заполняющих байта):

0001 0000001000 0001111011 0111001000 1001110

0010 000000101 00111001110 11100111001 000010

0100 00000011 01000101 10010010 10100011

0000 000000 11101100 00010001 11101100

разделите на 8-битные кодовые слова:

00010000 00100000 01111011 01110010 00100111 00010000 00010100 11100111

01110011 10010000 10010000 00001101 00010110 01001010 10001100 00000000

11101100 00010001 11101100 -> HEX 10207B72271014E77390900D164A8C0EC11EC

Напишите программу, чтобы прочитать 19 кодовых слов и вывести соответствующие данные.

Входные данные

Первая строка ввода содержит одно целое число P (1 le; P le; 1000), которое является количеством наборов данных, следующих далее. Каждый набор данных — это одна строка ввода, состоящая из номера набора данных N, за которым следует один пробел и 38 шестнадцатеричных цифр, представляющих 19 байт данных QR-кода. Допустимые шестнадцатеричные цифры: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E и F.

Выходные данные

Для каждого набора данных выводится одна строка. Она содержит номер набора данных (N), за которым следует один пробел, количество декодированных символов QR и строка символов, соответствующая данным QR-кода. В выходной строке печатные символы ASCII (в диапазоне 0x20 до 0x7e) выводятся как символы ASCII, ЗА ИСКЛЮЧЕНИЕМ того, что обратная косая черта (\) выводится как \, а знак фунта (#) выводится как \#. Непечатные 8-битные данные выводятся как \xx, где x — это шестнадцатеричная цифра (например, Æ). Непечатные 8-битные данные — это любые значения, которые меньше ASCII значения пробела (0x20) или больше 0x76. 13-битные значения кандзи выводятся как #bxxx, где b — это 0 или 1, а x — это шестнадцатеричная цифра (например, #13AC).

Примеры