칠 세그먼트 디스플레이

Tom은 과학자가 되는 것이 꿈인 소년으로, 여가 시간에 많은 것을 발명했다. 며칠 전 그는 직접 스톱워치를 만들겠다는 멋진 아이디어를 떠올렸다! 그래서 곧바로 칠 세그먼트 디스플레이를 샀다.

디스플레이의 일곱 소자는 모두 발광 다이오드(LED)이며, 서로 다른 조합으로 켜져 다음과 같이 아라비아 숫자를 나타낼 수 있다:

하지만 프로그램을 완성하고 스톱워치를 시험하려던 바로 그때, 일부 LED가 고장 난 것으로 드러났다! 일부 세그먼트는 절대로 켜지지 않았고 나머지는 정상적으로 작동했다. 이 때문에 디스플레이는 계속해서 모호한 상태를 표시했다...

Tom은 디스플레이가 만들어 낸 연속된 상태의 수열을 기록했으며, 이 디스플레이가 무엇을 하고 있었는지 알아낼 수 있는지 궁금해한다. 그는 첫 단계가 디스플레이가 다음에 표시할 상태를 알아내는 것이라고 생각한다. 그를 도와줄 수 있는가?

고장 난 세그먼트가 있더라도 디스플레이 자체는 정상적으로 작동한다는 점에 유의하라. 즉, 디스플레이는 어떤 수에서 시작하여 순환하며 계속 카운트다운한다(기록이 어디서 시작되었는지 알 수 없으므로 0-9 중 어느 것이든 될 수 있다). 여기서 '순환하며'란 디스플레이가 0에 도달할 때마다 다시 9부터 카운트다운을 계속한다는 뜻이다.

편의를 위해 아래 그림과 같이 디스플레이의 일곱 세그먼트를 A부터 G까지의 문자로 지칭한다:

예를 들어, 상태 기록이 다음과 같다고 하자:

ONLY 세그먼트 B가 고장 났고 디스플레이가 표시하려던 상태의 수열은 단순히 "9 -> 8 -> 7 -> 6 -> 5"라는 사실을 어렵지 않게 알아낼 수 있다. 그러므로 다음 수는 4여야 하지만, 세그먼트 B가 고장 난 것을 고려하면 다음 상태는 다음과 같아야 한다:

제한

테스트 세트당 시간 제한: 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 2000.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 5.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 100.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 Tom이 기록한 상태의 수를 나타내는 정수 N과, 공백으로 구분된 N개의 상태 목록을 포함하는 한 줄로 주어진다. 각 상태는 왼쪽부터 오른쪽까지 세그먼트 A-G의 표시를 나타내는 7자 문자열로 인코딩된다. 문자열의 각 문자는 '1' 또는 '0'이며, 각각 해당 세그먼트가 켜져 있거나 꺼져 있음을 나타낸다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이다. 입력으로부터 디스플레이의 다음 상태가 모호함 없이 결정된다면 y는 그 다음 상태여야 한다(입력과 같은 형식). 그렇지 않으면 y는 "ERROR!"여야 한다.