코코는 $M \times N$ 크기의 초콜릿을 $1 \times 2$ 또는 $2 \times 1$ 크기로 나누어 판매하려고 한다. 하지만 어느 날 코코의 친구 $K$명이 놀러 와서 $1 \times 1$ 초콜릿 한 칸씩을 떼어 먹어 버렸다. 남은 초콜릿을 나누었을 때 최대 몇 개의 초콜릿을 얻을 수 있는지 코코에게 알려주자.

Input

첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. 그 다음 줄부터 $T$개의 테스트 케이스가 순서대로 주어진다. 각 테스트 케이스의 첫 줄에는 $M$, $N$, $K$의 값이 주어진다. $M$은 초콜릿의 가로의 길이, $N$은 세로의 길이이다. 다음 $K$줄에는 각각의 친구가 떼어먹은 초콜릿 조각의 위치가 가로 좌표 $m$, 세로 좌표 $n$ 순으로 주어진다. 맨 왼쪽 위 칸의 좌표는 $(1, \,1)$이며, 초콜릿 조각의 위치는 중복되지 않는다.

Output

각 테스트 케이스에 대해, 주어진 초콜릿을 나누어 얻을 수 있는 $1 \times 2$ 또는 $2 \times 1$ 초콜릿의 개수의 최댓값을 한 줄에 출력한다.

Examples

Input 1

4
4 4 0
4 4 2
1 1
4 4
4 4 4
1 1
4 4
2 3
3 4
4 4 4
1 2
2 1
3 3
4 4

Output 1

8
6
6
5

Note

$1 \le T \le 1000$, $4 \le M, N \le 1000$, $0 \le K \le 4$, $M$, $N$은 $4$의 배수, $1 \le m \le M$, $1 \le n \le N$