#include <iostream>
#include <string>
#include <vector>

using namespace std;

/*
 * DEBUG ONLY: If compiled with -DDEBUG, then for each invalid puzzle in a
 * dataset the reason it is invalid gets printed to stderr.
 */

/* SANITY CHECK: used for assertion purposes to check for even/odd numbers */
#define odd(x)  ((x) % 2)
#define even(x) (!odd(x))

/*
 * SANITY CHECK: assertion macro for verifying input and internal state. Must
 * be used in a context where local variables "row" and "col" are defined.
 */
#define ASSERT(e) \
    { if(!(e)) { cerr << #e << " at " << row << "," << col << endl; throw; } }                                                      

/*
 * DEBUG ONLY: macro that prints out the details of why a particular puzzle
 * configuration is invalid. Must be used in a context where local variables
 * "row" and "col" are defined.
 */
#define INVALID(e) \
    { cerr << "INVALID: " << e << " at " << row << "," << col << endl; }

/* Maximum width and height as defined in the problem statement */
#define MAXSIZE 20

/* Encode the 4 adjacent directions we can to from any given cell or grid */
#define DIRS 4
int drow[DIRS] = { 0, 0, 1, -1 };
int dcol[DIRS] = { 1, -1, 0, 0 };

/*
 * Raw representation of the board as read in from the input. Line segments
 * visited by path_start() and path_next() are replaced with '*' to keep
 * track of them.
 */
char board[MAXSIZE * 2 + 1][MAXSIZE * 2 + 1];

/* Size of the current board in dots; i.e. 2*H+1 and 2*W+1 */
int rows, cols;

/*
 * For each cell containing a number, verify that the number of adjacent line
 * segments agrees with the number.
 */
bool verify_numbers(void)
{
    /* Iterate only over cells (not line segments or dots) */
    for(int row = 1; row < rows; row += 2) {
        for(int col = 1; col < cols; col += 2) {
            
            /* Only check cells with a number in them */
            if(board[row][col] != '?') {
                int count = 0;
            
                /* Convert '0', '1', '2' or '3' character to integer value */
                int number = board[row][col] - '0';
                ASSERT(number >= 0 && number <= 3);
                
                /* Check each of the 4 adjacent directions */
                for(int d = 0; d < DIRS; d++) {
                    char c = board[ row + drow[d] ][ col + dcol[d] ];
                    
                    /* Count any line segments present in this direction */
                    if(c == '-' || c == '|') {
                        count++;
                    }
                }
                
                /* The board is invalid if grid numbers don't agree */
                if(count != number) {
#ifdef DEBUG
                    INVALID("Bad number");
#endif
                    return false;
                }
            }
        }
    }
    
    /* If no problems found, then the board may yet be valid */
    return true;
}

/*
 * Find some horizontal line segment on the grid from which we can start
 * tracing the path. The line segment is marked as visited, the coords
 * (row,col) are set to the lattice dot immediately to the right of the line
 * segment, (srow,scol) to the coordinates immediately to the left of the
 * line segment, and true is returned. If no initial segment could be found,
 * then false is returned since the grid cannot possibly contain a valid loop.
 */
bool path_start(int &srow, int &scol, int &row, int &col)
{
    /* Iterate only over potential horizontal segments */
    for(srow = 0; srow < rows; srow += 2) {
        for(scol = 1; scol < cols; scol += 2) {
        
            /* The first horizontal line segment is our starting point */
            if(board[srow][scol] == '-') {
            
                /* Mark segment as visited */
                board[srow][scol] = '*';
                
                /* Continue traversal from the dot on the right */
                row = srow;
                col = scol + 1;
                
                /* The initial start point is dot to the left of line segment */
                scol--;

                return true;
            }
        }
    }
    
    /* A valid board must have at least one horizontal line segment somewhere */
#ifdef DEBUG
    cerr << "INVALID: No horizontal line segments found" << endl;    
#endif
    return false;
}

/*
 * Given the coordinate of some dot along the current path, verify that only
 * one unvisited segment exists from that dot. Mark the segment as visited,
 * advanve (row,col) to the other dot this line segment connects to, and
 * return true. If a dangler/cross over is detected at the current dot
 * or if no unvisited line segments are present (i.e. the path is not
 * connected) then return false.
 */
bool path_next(int &row, int &col)
{
    int count = 0, dir;

    ASSERT(board[row][col] == '#');

    /* Check each of the 4 adjacent directions */
    for(int d = 0; d < DIRS; d++) {

        int newrow = row + drow[d];
        int newcol = col + dcol[d];
        
        /* Do not check positions that go over the edge of the grid */
        if(newrow >= 0 && newcol >= 0 && newrow < rows && newcol < cols) {
            char c = board[newrow][newcol];

            /* Count any line segments present in this direction */
            if(c == '-' || c == '|') {
                dir = d; // Remember direction containing line segment */
                count++;
            }
        }
    }

    /* If no unvisited line segments are present, the path is not closed */
    if(count == 0) {
#ifdef DEBUG
        INVALID("Open path");
#endif
        return false;
    }
    
    /* More than one unvisited line segment, is a dangler or cross over */
    if(count != 1) {
#ifdef DEBUG
        INVALID("Dangler");
#endif
        return false;
    }
    
    /* Mark this line segment as visited */
    board[ row + drow[dir] ][ col + dcol[dir] ] = '*';
    
    /* Advance (row,col) to the next lattice dot along the path */
    row = row + drow[dir] * 2;
    col = col + dcol[dir] * 2;
    ASSERT(board[row][col] == '#');

    return true;
}

/*
 * Find an arbitrary line segment and try following the path. If the path is
 * a closed loop, does not cross itself, and does not contain any "danglers"
 * then return true. Each line segment reached on the path is replaced with
 * a "*" to mark that it has been visited.
 */
bool verify_path(void)
{
    int srow, scol; /* Starting dot position for path traversal */
    int row, col;   /* Current dot position for path traversal */

    /* Find starting position for path traversal */
    if(!path_start(srow, scol, row, col)) {
        return false;
    }

    /* Traverse path until we loop back to the starting point */
    while(row != srow || col != scol) {
        if(!path_next(row, col)) {
            return false;
        }
    }
    
    /* The path is intact so this may yet be a valid board */
    return true;
}

/*
 * Return false if any unvisited line segments are still left on the puzzle
 * since this indicates that another separate shape exists which could not
 * be reached by the path traversal.
 */
bool verify_visited(void)
{
    /* Iterate over all positions in the grid */
    for(int row = 0; row < rows; row++) {
        for(int col = 1; col < cols; col++) {
            char c = board[row][col];
            
            if(c == '-' || c == '|') {
#ifdef DEBUG
                INVALID("Extra path");
#endif
                return false;
            }
        }
    }
    
    /* If no unmatched line segments are left then the puzzle is valid */
    return true;
}

/* Main body of program */
void process(void)
{
    int board_num, board_idx;
    
    /* Read how many boards are to be analyzed */
    cin >> board_num;

    /* Process each board separately */
    for(board_idx = 0; board_idx < board_num; board_idx++) {
        int row = 0, col = 0;

        /* Read in the size of this board */
        cin >> rows >> cols;
        ASSERT(rows >= 0 && rows <= MAXSIZE);
        ASSERT(cols >= 0 && cols <= MAXSIZE);
        
        /* Convert from number of cells to number of dots */
        rows = rows * 2 + 1;
        cols = cols * 2 + 1;
        
        /* Read in board definition */
        for(row = 0; row < rows; row++) {
            for(col = 0; col < cols; col++) {
                char c;
                cin >> c;
                
                /*
                 * SANITY CHECK: Verify the correct characters are used in
                 * in the proper positions of the puzzle grid.
                 */
                if( even(row) && even(col) ) {
                    ASSERT(c == '#');
                }
                else if( even(row) && odd(col) ) {
                    ASSERT(c == '-' || c == '.');
                }
                else if( odd(row) && even(col) ) {
                    ASSERT(c == '|' || c == '.');
                }
                else /* odd(row) && odd(col) */ {
                    ASSERT(c == '?' || (c >= '0' && c <= '3'));
                }
                
                board[row][col] = c;
            }
        }
    
        /* Check if the puzzle is valid */
        bool valid = verify_numbers() && verify_path() && verify_visited();
        
        /* Print final result */
        cout << (valid ? "VALID" : "INVALID") << endl;
#ifdef DEBUG
        if (valid) {
            cerr << "VALID" << endl;
        }
#endif
    }    
}

/* Run program and print out any exceptions that occur */
int main(void)
{
    /* Throw exceptions on failed data extraction in >> operator */
    cin.exceptions(ios::failbit);
    
    /* Run main body of code */
    try {
        process();
    }
    
    /* Catch unexpected EOF or bad input data */
    catch(ios::failure const &e) {
        cerr << "Unexpected EOF or data type mismatch on input" << endl;
    }

    return 0;
}