The Sidewinder Sleeps Tonite

슬리더링크(Slitherlink)는 스도쿠를 전 세계에 널리 퍼뜨린 일본의 퍼즐 출판사 니콜리(Nikoli)가 유행시킨 논리 퍼즐이다. 규칙은 아주 단순하지만, 그럼에도 지독하게 어려운(그리고 즐거운) 퍼즐을 만들어 낼 수 있다.

슬리더링크의 규칙은 다음과 같다.

• 판은 점(격자점)들이 이루는 격자이며, 이 문제에서는 항상 규칙적인 직사각형 격자이다.
• 격자가 만드는 칸(cell) 중 일부에는 숫자가 적혀 있다. 직사각형 격자에서 이 숫자는 0 이상 3 이하이다.
• 가로 또는 세로로 인접한 두 점(칸의 변)을 선분으로 잇는다. 올바른 해답은 자기 자신과 교차하거나 닿지 않는 하나의 닫힌 고리(loop)를 이루어야 하며, 고리에 속하지 않는 선분(끊어진 선분이나 분리된 다른 고리)이 하나도 없어야 한다. 또한 숫자가 적힌 각 칸은 그 칸의 네 변 중 정확히 그 숫자만큼이 고리의 선분으로 사용되어야 한다.

풀렸다고 주장하는 슬리더링크 판이 주어진다. 이 판이 실제로 올바른 해답인지 판정하여라.

첫 줄에 데이터 집합의 개수 N ($1 \le N \le 100$)이 주어진다. 각 데이터 집합은 다음과 같이 주어진다.

• 두 정수 H, W ($1 \le H, W \le 20$)가 있는 줄. 각각 퍼즐의 높이와 너비를 (점이 아니라) 칸 수로 나타낸다.
• 이어서 판을 나타내는 $2H + 1$개의 줄. 다음 문자들만 사용한다.
  • 0, 1, 2, 3, ?: 칸 안에 적힌 숫자. ?는 숫자가 없는 칸을 뜻한다.
  • #: 격자의 점.
  • -, |: 인접한 두 점 사이의 가로 또는 세로 선분.
  • .: 인접한 두 점 사이에 선분이 없음.

모든 판은 빠짐없이 표기된다. 즉, 빈 칸이나 없는 연결을 나타내기 위한 줄 내부의 공백은 존재하지 않으며, 따라서 각 줄은 정확히 $2W + 1$개의 문자로 이루어진다.

각 데이터 집합에 대해, 주어진 슬리더링크의 올바른 해답이면 VALID를, 아니면 INVALID를 각각 한 줄에 출력한다.