Nine Knights

In the game of chess, knights are underwhelming but unique. No other piece moves like the knight in its 'L' shaped pattern. The knight moves in an L shape in any direction. It either moves two squares sideways and then one square up or down, or two squares up or down and then one square sideways.

Figure 1: The highlighted squares show all possible moves for a knight.

The knight changes the color of its square with each move. If it starts on a light square, it lands on a dark square after its move. In the diagram, the knight can move to any of the red squares.

The maximum number of knights that fit on a board is given by:

In the nine knights puzzle, nine knights are placed on a 5 by 5 board, even though up to thirteen fit. The knights are placed so that none of them attack one another. The board below shows an invalid solution:

...k.
...k.
k.k..
.k.k.
k.k.k

The first line contains the number of test cases. Each test case is a 5 by 5 board given as five lines of characters. Each line consists only of '.' and 'k'. The '.' character is an empty square and 'k' is a knight. There is no blank line between boards.

Print one line for each test case. Print "valid" if the given board is a valid solution to the nine knights problem. Otherwise, print "invalid".