Boltu loves puzzle very much. He solves different types of puzzle problems in different online judges. Sometimes he teaches his small brother Gultu how to solve puzzle. But Gultu is not very good at this. One day Boltu made a puzzle for Gultu. It’s a number puzzle. A board contains N rows & M columns. Each of the cells of this board contains a square shaped disk. Each disk contains a random number between 0 to (N*M)-1. These numbered disks are placed randomly. You have to put these disks in ascending order. Moving these disks always maintains a rule. You must put off two disks at a time & place them. Gultu says that it seems too easy. Boltu says yes it is. But you have to solve it in minimum move. After sometime he did it & very excited. If Gultucan solve it then you must do that.

For 3x3 board.it needs minimum 6 moves to do so.

TO

Input

Input starts with an integer t<=100. Each input takes two integers N<=100& M<=100 where N represents row & M represents column. Then input N*M integers where each row contains M numbers.

Output

For each input the output line shows case number and minimum moves needed to solve this.

Sample:

Authored By: Tanvir Hasan Anick