## Yuvraj and Game

Time Limit: 5 sec
Memory Limit: 256 MB
Attempts: 1
Accuracy: 100.00%
Author: Akashdeep Goel

Yuvraj loves cricket and regularly plays with his friends but yesterday, one of his legs got fractured and now he is not able to go out and play. So, he decided to play an android game similar to cricket but this game is a little different from what the actual game is. In this game, there is an N*M matrix(field) and some players are randomly standing in the matrix to block the ball and stop the game. The ball starts to move from the first row and it can move either diagonally or vertically in the next row. Any movement in the same row or to the previous row is restricted. Considering the distance between any two rows as one unit, Yuvraj has to tell the maximum number of units (vertical row-wise distance) the ball can travel.

For example let # be the players and 0 be free path in the below matrix :-

0 # 0 0

0 # # #

# 0 # #

0 # # #

# # 0 #

In this matrix, a player starting from first row first column can at maximum, go upto 4 rows.

### Input

First line contains T, the number of test cases.

For each test case, first line contains number of rows N, number of columns M.

Next line contains number of players K.

Next K lines contain the coordinates of the form (a,b) at which the players are standing.

### Output

For each test case, print the correct answer given by Yuvraj in new line.

### Constraints

### 1<=T<=10

### 1<=N<=1,000

### 1<=M<<=100

### 0<=K<=N*M

### 1<=a<=N

### 1<=b<=M

### Example

### Input:

2

2 2

2

1 1

1 2

5 3

9

1 1

1 3

2 1

2 2

3 3

4 2

5 1

5 2

5 3

### Output:

0

4
ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED

6 months ago

cpp

0.00 sec

0 KB

2 years ago

cpp

0.07 sec

64 KB

2 years ago

python

0.07 sec

64 KB

2 years ago

python

0.07 sec

64 KB