Minimum Moves to Collect Treasures

Problem Description

Bob is given a grid with P rows and Q columns. In the grid, there are certain cells that contain treasures. The treasures are located at different coordinates, given as pairs of integers.

Bob can choose any cell in the grid to start. His goal is to collect all the treasures. The twist is that Bob wants to minimize the total number of moves required to collect all the treasures. A move is defined as a unit step in the grid in any direction. It turns out that the minimum number of moves required, if Bob picks the optimal starting cell, can be computed using the following formula:

$$ \text{moves} = \max(x_{max} - x_{min},\; y_{max} - y_{min}) $$

Here, \(x_{min}\) and \(x_{max}\) are the minimum and maximum row coordinates of the treasures, and \(y_{min}\) and \(y_{max}\) are the minimum and maximum column coordinates respectively. If there is only one treasure, Bob can simply begin at that cell, making the number of moves equal to 0.

Your task is to compute the minimum number of moves required for Bob to collect all treasures for each given test case.

inputFormat

Input Format

The first line contains an integer T denoting the number of test cases.

Each test case is described as follows:

• The first line contains three integers P, Q, and K, where P is the number of rows, Q is the number of columns, and K is the number of treasures.
• The next K lines each contain two integers representing the coordinates of a treasure.

Note: The input is read from standard input (stdin).

outputFormat

Output Format

For each test case, output a single integer on a new line, which is the minimum number of moves required for Bob to collect all the treasures. The output must be written to standard output (stdout).

## sample

2
3 3 1
2 2
3 3 2
1 1
3 3

0
2

</p>