The Sidewinder Sleeps Tonite

Slitherlink is a logic puzzle popularized by the Japanese puzzle publisher Nikoli, the same company that made Sudoku famous around the world. It has a very small set of rules that can nonetheless produce devilishly difficult (and delightful) puzzles.

The rules of Slitherlink are as follows:

• The board is a lattice of dots. In this problem the lattice is always a regular rectangular grid.
• Some of the cells formed by the lattice contain a number. On a rectangular lattice each such number is between 0 and 3 inclusive.
• You draw line segments that connect horizontally or vertically adjacent dots (the sides of the cells). A correct solution forms a single closed loop that never crosses or touches itself, with no segments that are not part of the loop (no dangling segments and no additional separate loops). In addition, every numbered cell must have exactly that many of its four sides used by the loop.

You are given a Slitherlink board that is claimed to be solved. Determine whether it is indeed a legitimate solution.

The first line contains a single integer N ($1 \le N \le 100$), the number of data sets. Each data set is given as follows:

• A line with two integers H and W ($1 \le H, W \le 20$): the height and width of the puzzle measured in cells (not dots).
• Then $2H + 1$ lines describing the board, using only the following non-whitespace characters:
  • 0, 1, 2, 3, ?: the number written inside a cell; ? marks a cell with no number.
  • #: a dot of the lattice.
  • -, |: a horizontal or vertical line segment between two adjacent dots.
  • .: an absent connection between two adjacent dots.

Every board is written out in full: a line never contains internal whitespace to stand for an empty cell or a missing connection, so each of the $2H + 1$ lines has exactly $2W + 1$ characters.

For each data set, print VALID if the board is a correct solution of the given Slitherlink, or INVALID otherwise. Print each answer on its own line.