Reading UPC Barcodes

Youngwoo, the logistics manager at FoodVictory, has lost part of a barcode database. To avoid serious trouble, he needs to recover every valid UPC-A code that could match a damaged barcode image.

A UPC-A barcode represents a 12-digit decimal number. It is encoded as 95 bits of alternating light and dark bars, with the structure SLLLLLLMRRRRRRE.

• S is the start pattern 101.
• M is the middle pattern 01010.
• E is the end pattern 101.
• Each L pattern corresponds to one of the first 6 decimal digits.
• Each R pattern corresponds to one of the last 6 decimal digits.

Bit 1 means a dark bar, and bit 0 means a light bar. Each digit pattern has 7 bits, so the code portion has length 3 + 6*7 + 5 + 6*7 + 3 = 95. A real barcode also has at least 9 light bars on both sides, but the input contains only the 95 code bits.

The last decimal digit is the check digit. Let digitN be the N-th decimal digit and check_digit be the last digit. The check digit is computed as follows.

CheckSum = 3*(digit1 + digit3 + digit5 + digit7 + digit9 + digit11) + digit2 + digit4 + digit6 + digit8 + digit10;
Code = CheckSum % 10;
If (Code == 0) check_digit = 0;
else check_digit = (10 - Code);

A barcode scanner reads a narrow image of the barcode and infers the 95 code bits from that image. If the barcode is scanned upside down, the bit string is read in the opposite direction. Also, low contrast or reflections may make some bits impossible to determine.

A damaged barcode is given as a length-95 string made of 0, 1, and ?. A ? means that the bit is damaged and unknown. Print every valid UPC-A code that can match the given string. You must also consider the case where the bit string was read in reverse.

The first line contains the number of test cases T. Each test case consists of two lines. The first line contains the first 50 characters of the barcode bit string, and the second line contains the remaining 45 characters.

For each test case, first print the number of valid barcodes that match the input. If more than 8 barcodes match, print 9 instead of the actual count.

Then print the matching barcodes in increasing order, one per line. If 9 or more barcodes match, print only the first 8.