SP1267 ORIGLIFE - Origin of Life

Conway's _Game of Life_ is not really a game, but a _cellular automaton_ -- a set of rules describing interactions among adjacent cells on a grid. In our game, we have an _n_ by _m_ rectangular grid of cells identified by integer coordinates (_x, y_). The game progresses through a series of steps; at each step a new _generation_ is computed from the current _generation_. The game begins with the _first generation_. In any given generation, which we shall call the current generation, each cell is either _live_ or _dead_. In the next generation, each cell's status may change, depending on the status of its immediate neighbours in the current generation. Two distinct cells (_x $ _{1} $ , y $ _{1} $_ ) and (_x $ _{2} $ , y $ _{2} $_ ) are immediate neighbours if they are horizontally, vertically, or diagonally adjacent; that is, if |_x $ _{1} $ - x $ _{2} $_ ≤ 1| and |_y $ _{1} $ - y $ _{2} $_ ≤ 1|. Each cell that is not on the border of the grid has eight immediate neighbours. There are three integer parameters (_a, b, c_) which affect the game. The rules of the game are: - If a live cell has fewer than _a_ live neighbours in the current generation it dies of loneliness. That is, it is dead in the next generation. - If a live cell has more than _b_ live neighbours in the current generation it dies of overcrowding. That is, it is dead in the next generation. - If a dead cell has more than _c_ live neighbours in the current generation it is born. That is, it is live in the next generation. - Otherwise, a cell's status is unchanged from the current generation to the next. This process continues indefinitely. Eventually, a generation may be repeated in which case life goes on forever. Or all the cells may die. Similarly, if we explore previous generations that may have led to the current one, we may find one that is necessarily a first generation; that is, it could not have been created from a previous generation by following the rules. Such a generation is known as a Garden of Eden. Given the game parameters and the current generation, you are to determine whether or not the game might have started with a Garden of Eden. If so, output the number of steps necessary to reach the current generation from the Garden of Eden. If there are several possible answers, find the smallest. If there is none, output -1.

Input begins with a single integer, the number of test cases. For each test case, there are _m_+1 lines of input in total. The first line contains the game parameters, which are five integers _m,n,a,b,c_ each separated by one space. The constraints are 1≤_m_≤4, 1≤_n_≤5, 1≤_a_

Output is one integer per test case denoting the minimum number of steps required to reach the input from a Garden of Eden. If there is no Garden of Eden, output -1.