Molecules, Molecules 2

Organic molecules get amazingly complex, and drawing them takes a great variety of shapes and conventions, especially if we want to show their three dimensional structure. If we restrict ourselves to reasonably simple compounds, meaning those with only single bonds between atoms, we can lay them out on a simple rectangular grid with every bond running horizontally or vertically. In such a molecule carbon bonds to 4 adjacent atoms, nitrogen to 3, oxygen to 2 and hydrogen to 1. Not every grid describes a valid molecule. Write a program that decides whether a given grid does.

An atom bonds only with the atoms directly above, below, left or right of it, and two adjacent atoms do not have to bond. The grid is valid when you can pick a set of bonds that gives every atom on the grid exactly the number of bonds it needs.

The input consists of a series of candidate molecules drawn as grids. The first line for each molecule has two integers $r$ and $c$ ($1 \le r, c \le 20$), the number of rows and columns of the rectangle that follows. The next $r$ lines contain $c$ characters each, where each character is one of '.' (empty), 'H' (hydrogen), 'O' (oxygen), 'N' (nitrogen), 'C' (carbon). The input ends with a line holding two zeroes, 0 0. A molecule classified as valid need not be physically realisable, and one grid sometimes holds more than one molecule.

For each candidate molecule, print one of these two lines:

Molecule <num> is valid.
Molecule <num> is invalid.

where <num> is a running number starting at 1.