나무 블록

서로 다른 8종류의 나무 조각을 한 줄로 이어 붙여 직사각형을 만드는 게임이다. 각 조각은 왼쪽 면과 오른쪽 면을 가지며, 각 면의 모양은 다음 다섯 가지 중 하나이다.

• 평평함(flat): 아무것도 없는 평평한 면
• 사각 볼록(square-out): 사각형 모양으로 튀어나온 돌기
• 사각 오목(square-in): 사각형 모양으로 파인 홈
• 원형 볼록(round-out): 둥근 모양으로 튀어나온 돌기
• 원형 오목(round-in): 둥근 모양으로 파인 홈

두 조각이 서로 맞물리려면, 왼쪽 조각의 오른쪽 면과 오른쪽 조각의 왼쪽 면이 같은 모양의 볼록–오목 쌍이어야 한다. 즉, 사각 볼록은 사각 오목과만, 원형 볼록은 원형 오목과만 맞물린다.

8종류 조각의 왼쪽 면과 오른쪽 면은 다음과 같다.

올바른 배치는 다음 조건을 모두 만족해야 한다.

1. 가장 왼쪽 조각은 1번 조각이고, 가장 오른쪽 조각은 2번 조각이다.
2. 인접한 두 조각은 서로 맞물려야 한다.
3. 전체 배치에서 가장 왼쪽 면(1번 조각의 왼쪽)과 가장 오른쪽 면(2번 조각의 오른쪽)은 평평하며 아무 조각과도 맞물리지 않는다.
4. 위 조건이 지켜지면, 각각의 1번 조각에는 대응하는 2번 조각이, 각각의 5번 조각에는 대응하는 6번 조각이 항상 존재한다.

세희는 이 게임을 앱으로 만들고 있다. 사용자가 배치한 조각들이 위 조건을 만족하는 올바른 배치인지 판별하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 하나씩 주어지며, 한 줄에는 왼쪽부터 오른쪽 순서로 조각의 번호(1부터 8까지)가 공백 없이 이어져 있다. 한 테스트 케이스에는 적어도 1개의 조각이 있고, 조각의 개수는 10,000개를 넘지 않는다.

입력의 마지막 줄에는 0이 하나 주어지며, 이는 입력의 끝을 의미한다.

각 테스트 케이스마다 테스트 케이스 번호(1부터 시작)를 출력한 뒤, 주어진 배치가 올바르면 VALID, 올바르지 않으면 NOT을 출력한다. 출력 형식은 번호. 결과이며, 번호 뒤에는 마침표와 공백 하나가 온다.