Atoms is a two player game consisting of an N ∗ N grid. The top-left cell has a coordinate of (0, 0) and the bottom-right has a coordinate of (N − 1, N − 1). Each player has an infinite number of atoms with them. Every atom of player one has the same color. The atoms of player two also have same color but they are different from those of player one. The two players take turns to place atoms on the grid. On each turn, a player selects a stable cell to place one atom from his collection. The rule for stability is simple; the cell must either be empty or it must already contain an atom of that players color. There is however an upper limit to the number of atoms a cell may contain and they are described below: i) The four corner cells can contain at most 1 atom. ii) The other outer cells can contain at most 2 atoms. iii) The remaining cells can contain at most 3 atoms. As an example, the figure above shows a grid of 5 × 5. The filled cells can contain at most 1 atom each. The stripped ones can contain at most 2 atoms each and the blank ones can contain at most 3 atoms each. When selecting a stable cell, the two players follow rather simple rules: i) First, player one places an atom on a randomly selected cell. ii) Player two looks for a cell whose minimum distance from any cell occupied by atoms of player one is maximized. Here distances between cells are measured as Manhattan distance. The Manhattan distance between two cells is the sum of the absolute row difference and column difference. For example, the Manhattan distance between (1, 5) and (4, 2) is equal to (4-1) + (5-2) = 3 + 3 = 6. iii) In case of multiple cells fulfilling the criteria of rule (ii), the cell with lowest row number is selected. If there is still a tie, then the cell with lowest column number is selected. iv) Player one then follows a similar strategy to that described in (ii) to place another atom and the game continues likewise. If a player is unable to make any valid move, then he is considered the loser and the game stops there. Your task in this problem is simple. Given a state of the grid, you are to determine if this state is achievable if the players follow the rules mentioned earlier.
2/2 Input The first line of input will start with a positive integer T < 50, where T denotes the number of test cases. Each case will begin with a number N (3 ≤ N ≤ 7) which denotes the size of the grid for that case. N lines will follow with N integers on each line. The absolute value of these integers will be less than 107. A positive integer means player one has placed atoms in the corresponding cell and negative integer means player two placed atoms in the cell. The number of atoms in a cell is denoted by the absolute value of the cell. Output For each case, output the case number first. If the given configuration is valid output ‘valid’, otherwise output ‘invalid’. Look at the sample in/out for exact format. Sample Input 2 3 100 000 0 0 -1 3 200 000 000 Sample Input Case 1: valid Case 2: invalid