You are about to finish your favorite game ...(put the name of your favorite game here). Now there is just one hard quest before you can unlock the last level. Or a shortcut. As the quest is too hard you were wondering whether you can solve the shortcut. The shortcut is to solve a puzzle. The puzzle is given as an m × n grid of integer from 1 to m ∗ n. You have to rearrange it so that the grid is sorted. That is the first row contains 1 to n. Second row contains n + 1 to 2n. And so on. Thus last row contains mn−n+1 to mn. 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. For example the following grid will be read as 1-2-10-11-9-15-16-3-14-12-13-4-8-17-7- 518-19-6-20 and it will be transformed into the grid shown in below. Now you are wondering given the initial configuration how long it will take to solve the puzzle or it is impossible to solve. Input Input starts with an integer T ≤ 70. T test cases follow. Each test case starts with two positive integer m, n ≤ 200. You may assume that the m, n will be such that any solvable puzzle of grid size m × n can be solved within 2 ∗ 1018 steps. Then follows m lines, each of these lines contains n integers. j-th integer of i-th is (i,j)-th entry of the grid. You may assume that the grid consists of all number between 1 to (n ∗ m) exactly once.
2/2 Output For each case print one line containing number of steps needed to reach the solution or ‘-1’ if solution cannot be reached. Sample Input 4 34 1234 5678 9 10 11 12 34 1267 3 5 8 11 4 9 10 12 34 1 2 3 11 5 6 10 9 8 7 4 12 34 1259 6347 10 11 8 12 Sample Output 0 1 3 5