SP3647 MOEBIUS - Moebius

[English](/problems/MOEBIUS/en/) [Vietnamese](/problems/MOEBIUS/vn/) The game of Moebius is not well known, but there are some fanatics who spend their whole day playing it. In this game, the player is to find the way to clear a pair of squares containing x and z on a Moebius with the minimum cost. A Moebius is made from a rectangular M×N paper, namely ABCD. Each face of this paper consists of a rectangular grid of equivalent squares 1×1 . On both grids, columns are sequentially numbered from 1 to N and rows are sequentially numbered from 1 to M, all starting at A corner. In addition, every square (i, j), located at row i and column j, can contain x, z or nothing (empty square). Taking this paper and giving it a half-twist, then joining the ends together, A with C and B with D, to form a single band, we have a Moebius, which has only one surface, for this game.    One clearance of a pair of squares containing x and z could be executed only if there is a direct path between two squares through consecutive 4 neighboring empty squares with at most two left or right turns. The intermediate empty squares may locate out of the Moebius. The cost to clear a pair of squares containing x and z is the length of the shortest direct path between two squares. After a clearance, the two original squares containing x and z become empty. The figure above shows two consecutive clearances with the cost of 5 and 8 respectively. Your task is to write a program to perform one clearance to remove a given pair of squares containing x and z, with the minimum total cost using at most one extra intermediate clearance.

The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets. For each data test, the first line contains 2 integers M and N (1

For each data test, write in one line the minimum total cost. Write '-1' if the given pair cannot be cleared using at most one intermediate clearance.