A. Arthur The Ant
time limit per test
3 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Arthur the ant lives in a beautiful garden that contains a large pond containing multiple lily pads. The pond can be described as an $$$n \times m$$$ grid containing $$$k$$$ lily pads. The $$$i$$$-th lily pad is located at position $$$(x_i, y_i)$$$ on the pond. There are always lily pads on location $$$(1,1)$$$ and $$$(n,m)$$$.

Arthur is located at position $$$(1,1)$$$ but he wants to walk to position $$$(n,m)$$$. As ants cannot swim he must wait for the lily pads to grow. During each day the lily pads will expand to all neighbouring locations, that is, if at day $$$j$$$ location $$$(a,b)$$$ is covered by a lily pad, then in day $$$j+1$$$ locations $$$(a+1, b), (a-1, b), (a, b+1)$$$ and $$$(a, b-1)$$$ will also be covered by lily pads.

Arthur can walk to neighbouring locations that contain lily pads. If Arthur is located at position $$$(a,b)$$$ then he can walk to locations $$$(a+1, b), (a-1, b), (a, b+1)$$$ and $$$(a, b-1)$$$ if they are covered by a lily pad.

Arthur isn't the smartest ant, so he asks you how many days does he have to wait until there exists a path from $$$(1,1)$$$ to $$$(n,m)$$$ that contains lily pads.

Input

Each test contains multiple test cases. The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 5 \cdot 10^4)$$$, the number of test cases. The description of the $$$t$$$ test cases follow.

The first line of each test case contains three integers $$$n, m, k$$$ ($$$1 \leq n,m \leq 10^9, 2 \leq k \leq 10^5$$$), the dimensions of the pond and the number of lily pads.

The next $$$k$$$ lines of each test case contain two integers $$$x_i, y_i$$$ ($$$1 \leq x_i \leq n, 1 \leq y_i \leq m$$$), corresponding to the location of the $$$i$$$-th lily pad.

It is guaranteed lily pads $$$(1,1)$$$ and $$$(n,m)$$$ are always contained in the input, and that the sum of $$$k$$$ over all test cases does not exceed $$$10^5$$$. It is also guaranteed that $$$n = m = 1$$$ will never happen.

Output

For each test case, output the minimum number of days that Arthur has to wait until there exists a path from $$$(1,1)$$$ to $$$(n,m$$$) that contains lily pads.

Example
Input
1
5 6 4
1 1
2 4
2 6
5 6
Output
2
Note

Visualization of test case 1

After 0 days
After 1 day
After 2 days : There exists a path now from (1,1) to (5,6)