Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9 × 9 grid so that each column, each row, and each of the nine 3 × 3 boxes (also called blocks or regions) contains the digits from 1 to 9 only one time each. The puzzle setter provides a partially completed grid.[from wikipedia] Left figure is the puzzle and right figure is one solution for that puzzle. It’s a very common game for magazine and newspapers, and people like it for killing time. How about adding some features to this game, some cells can only be filled with even number, some cells can only be filled with odd number, and some cells can only be filled with the same number. Great, let’s call it “Sudoku Extension”. It’s very easy to give one possible solution a Sudoku Extension puzzle, but do you know how many solutions are there for a certain Sudoku Extension problem? Let’s find out! Input The input data will start with the number of test cases. For each test case, 9 lines followed, correspond- ing to the rows of the table. On each line, a string of exactly 9 characters is given, it’s either 0-9 digit, or a-z alpha in lower case. ‘1’ - ‘9’ means the cell is already filled in; ‘0’ means this cell is empty; ‘e’ means the cell need to be filled with a even number; ‘o’ means the cell need to be filled with an odd number; other alpha of ‘a’ - ‘z’, except ‘e’ and ‘o’ denote a variable, so if two or more cells denoted by ‘a’, then they must be filled with the same number. Output The output for each case is the number of possible solutions, note for each case, the solution will be less than 3000, and there are not more than 10 test cases. Sample Input 1 040008007
2/2 00e030408 006000200 301004000 0080000o2 000003000 200401005 600070000 800006003 Sample Output 507