나무 블록

블록은 아래와 같은 나무 조각 8개를 이용해서 하는 게임이다.

이 게임의 목표는 아래와 같은 조건을 지키면서 주어진 나무 조각을 이용해 가장 넓은 직사각형을 만드는 것이다.

1. 가장 왼쪽 조각은 1번 조각, 가장 오른쪽 조각은 2번 조각이어야 한다.
2. 인접한 조각은 서로 맞물려야 한다. 예를 들어, 4번 조각과 5번 조각은 항상 1번 조각의 오른쪽에 있어야 한다. 또, 4번 조각은 1번이나 3번조각의 오른쪽에 있을 수 있다.
3. 1번 조각의 왼쪽과 2번 조각의 오른쪽에 맞물리는 조각은 없다.
4. 각각의 1번 조각에 대해서, 대응하는 2번 조각이 있어야 하고, 5번 조각에 대해서도 대응하는 6번 조각이 있어야 한다.

예를 들어, 아래 2가지는 올바른 배치이다.

하지만, 아래 세 가지는 올바르지 않다.

세희는 이 게임을 앱으로 만들고 있다. 지금 구현할 부분은 사용자가 맞춘 블록이 문제의 조건에 올바른지 아닌지 판별하는 것이다.

한 사용자가 맞춘 블록 게임의 결과가 주어졌을 때, 올바른지 아닌지 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄에 하나씩 주어진다. 각 조각은 문제의 그림에 나와있는 숫자로 주어진다. 숫자는 공백없이 주어진다. 적어도 1개의 조각이 주어지며, 조각 10,000개를 넘기는 경우는 없다.

입력의 마지막 줄에는 0이 하나 주어진다.

각각의 테스트 케이스에 대해서, 테스트 케이스 번호(1부터 시작)를 출력하고, 입력으로 주어진 배치가 올바르면 "VALID", 아니면 "NOT"을 출력한다.