You are about to finish your favorite game... (put the name of your favorite game here). And now you are on the last level. You have almost finished it but there is one hard quest that you want to avoid. So again you are going for shortcut. The shortcut is again to solve a puzzle. The puzzle is given as an m × n grid where each cell colored in red, blue or green. You are also given a target grid. You have to change given grid the to the target grid. The only allowed operation is pressing a switch. After some trial and error you figured out how the switch works. It rearranges the element by reading them by one diagonal after another. And put them back row wise. See he tables below for details. Then each cell is recolored using following rule: A cell (i, j) is recolored only if (i + j) is even. (The cells are numbered (1, 1) for the left top point and (m, n) for the right bottom point). However, no cells in bottommost row or rightmost column are recolored, even if (i + j) is even. For recoloring 3 cells are considered. The cell right to it, the cell below it and the cell itself. The recoloring rule is color(current, below, right) = f (current, f (below, right)). Where the f function is defined by following table. For example the following grid will be read as RBBRGRGBBBRRBBRRBGGG and it will be transformed into the grid shown in below. Initial grid After rearrangement
2/3 After recoloring Now you are wondering given the initial configuration how long it will take to solve the puzzle or whether it is impossible to solve in fewer than 224 steps. Input Input starts with an integer T ≤ 100. T test cases follow. Each test case starts with two positive integers m, n (3 ≤ m, n and m ∗ n ≤ 25). Then follows m lines, each containing n space separated characters, representing the initial grid. Then follows another m lines, each containing n space separated characters, representing the target grid. Both grids are followed by an empty line. See Sample IO for detail. Output For each case print one line containing number of steps needed to reach the solution or ‘-1’ if solution can not be reached in less than 224 steps. Sample Input 3 45 RBRGB BGBBR RBRRG BRBGG BBGRG RRBRB RRBBR RBGGG 33 RRR RRR RRR RRR RRR RRB 33 RRR RRR
3/3 RRR RRR RRR RRR Sample Output Case 1: 1 Case 2: -1 Case 3: 0