Minimum Moves on a Toroidal Grid

You are given a grid with r rows and c columns that behaves as a torus (i.e., it wraps around both vertically and horizontally). A ball is placed at a starting cell and needs to reach a target cell. In one move, the ball can move to an adjacent cell (up, down, left, or right) with wrap‐around allowed. Given a maximum number of moves k, your task is to determine the minimum number of moves required to reach the target cell. If the target cannot be reached within k moves, output -1.

The distance is calculated on the torus. More precisely, for the vertical and horizontal directions, the effective distance is the minimum between the direct distance and the wrap-around distance. The minimum moves is the sum of these two distances. If the computed moves is less than or equal to k, then the ball can reach the target cell using the calculated number of moves; otherwise, it is impossible and the output should be -1.

Note: The grid cells are given in 1-indexed format.

inputFormat

The input is read from stdin and has the following format:

T
r c k
sr sc
tr tc
... (repeated T times)

Where:

• T is the number of test cases.
• For each test case:
• r c k: the number of rows, columns, and the maximum number of moves allowed.
• sr sc: the starting row and column (1-indexed).
• tr tc: the target row and column (1-indexed).

outputFormat

The output should be printed to stdout and consists of one or more lines. Each line represents the answer for a test case. For each test case, output the minimum number of moves needed to reach the target cell. If it is not possible to reach the target cell within k moves, output -1.

## sample

3
3 4 5
3 2
1 4
2 2 0
2 2
2 2
5 5 8
3 3
1 1

3
0
4

</p>