Barcode of Judgment

While stuck in traffic, I spot an ad on a nearby taxi for an intriguing restaurant. The ad carries an embedded 2-D barcode, so I photograph it with my phone; the phone reads the code and hands me a web address with a map to the nearest location.[1]

Given an "image" of a 2-D barcode, determine the text string it encodes.

A 2-D barcode has both fixed and variable parts. In the diagram below, fixed cells are drawn as 0 or 1, and variable (data) cells are drawn as -:

1010---01
1000---00
10-------
10-------
10-------
1000---00
101000001

The variable cells hold the data. When the barcode is in the orientation shown above (7 rows by 9 columns, i.e. 30 data cells), the data cells are read left-to-right, top-to-bottom.

For example, given this barcode:

101000101
100011000
100100010
101101011
100111011
100011000
101000001

the data bits, read in order, are:

001110010001011010110111011110

Split them into 5-bit chunks:

00111 00100 01011 01011 01110 11110

Convert each chunk to its decimal value:

7 4 11 11 14 30

Finally, decode each value with this table:

So this barcode decodes to hello!. Every barcode encodes exactly 6 characters (30 data bits ÷ 5 = 6).

The first line contains an integer $N$ ($1 \le N \le 100$): the number of data sets.

Each data set begins with a line H W, where $H$ ($7 \le H \le 80$) and $W$ ($9 \le W \le 80$) are the height and width of the image. The next $H$ lines each contain $W$ binary digits (0 or 1) representing the black-and-white image your camera captured.

Any barcode that appears in the image was photographed square-on, but it may have been rotated by any multiple of 90 degrees.

For each data set, print one line:

• If the image contains exactly one valid barcode, print its decoded value.
• If the image contains no valid barcode, print NOCODE.
• If the image contains more than one valid barcode — so the genuine one cannot be identified — print INTERFERENCE.

[1] Rekimoto, Jun and Ayatsuka, Yuji. 2000. CyberCode: Designing Augmented Reality Environments with Visual Tags. Sony Computer Science Laboratories, Inc.