Broken Seven-segment Display

Time limit5sMemory limit512 MB

Summary

From N recorded seven-segment states of a countdown with unknown start digit and stuck-off segments, find the single possible next state or report ERROR!.

Level: Medium5 of 10
Topics: Brute force, Bit manipulation, Simulation
Solved: No attempts yet

Problem

Tom is a boy who wants to become a scientist. A few days ago he decided to build a stopwatch himself, so he bought a seven-segment display.

The seven segments of the display are light-emitting diodes, and lighting them in different combinations shows the digits 0 to 9.

For convenience the seven segments are named A to G as in the picture below.

A state of the display is written as a string of length 7. The characters give the segments A, B, C, D, E, F, G in that order, where 1 means the segment is lit and 0 means it is off. The ten digits are shown like this.

Digit	Lit segments	State
0	A, B, C, D, E, F	`1111110`
1	B, C	`0110000`
2	A, B, D, E, G	`1101101`
3	A, B, C, D, G	`1111001`
4	B, C, F, G	`0110011`
5	A, C, D, F, G	`1011011`
6	A, C, D, E, F, G	`1011111`
7	A, B, C	`1110000`
8	A, B, C, D, E, F, G	`1111111`
9	A, B, C, D, F, G	`1111011`

When Tom finished his program and tested the stopwatch, some segments turned out to be broken. A broken segment never lights up, no matter which digit the display shows, and every other segment works normally. Tom does not know which segments are broken.

The display keeps working despite the broken segments. It starts from some digit and counts down by one, cyclically: after showing 0 it starts counting down from 9 again. Tom does not know where his record starts, so the first digit can be any of 0 to 9.

Tom wrote down $N$ consecutive states that the display produced. Find the state the display shows right after that record.

Input

The first line contains the number of test cases $T$ .

Each test case is one line. It contains the number of recorded states $N$ and then the $N$ states, separated by spaces, in the order the display produced them.

$1 \le T \le 2000$
$1 \le N \le 100$
Each state is a string of length 7 made of 0 and 1.
Every record is explained by at least one pair of a starting digit and a set of broken segments.

Output

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1.

If every explanation of the record gives the same next state, $y$ is that state, written in the same format as the input. If the record has several explanations that give different next states, $y$ is ERROR!.

Examples2

Example 1

Input

4
1 1111111
2 0000000 0001010
3 0100000 0000111 0000011
5 1011011 1011111 1010000 1011111 1011011

Expected output

Case #1: 1110000
Case #2: ERROR!
Case #3: 0100011
Case #4: 0010011

Example 2
Input
```
1
1 0000000
```
Expected output
```
Case #1: ERROR!
```