디스코 댄스 대소동

대릴은 디스코 댄스 덴이라는 디스코 클럽을 운영한다. 이 클럽의 무대는 $m \times n$ 격자이고, 처음에는 모든 칸에 불이 켜져 있다. 음악이 시작되면 그중 일부 칸의 불이 꺼진다.

디스코 댄스는 음악이 흐르는 동안 밟는 두 걸음 이상의 동작이다. 디스코 댄스의 마지막 걸음은 무용수가 처음 서 있던 칸을 밟아야 한다.

무용수는 춤추는 동안 불이 켜진 칸만 밟는다. 켜진 칸을 밟는 순간 그 칸의 불은 꺼진다. 또 무용수는 다음 네 조건을 항상 지킨다.

1. 한 걸음마다 왼발과 오른발을 번갈아 쓴다. 두 발을 동시에 움직이지 않는다.
2. 왼발을 옮길 때는 오른발과 같은 열에 있으면서 불이 켜진 칸을 밟는다.
3. 오른발을 옮길 때는 왼발과 같은 행에 있으면서 불이 켜진 칸을 밟는다.
4. 첫 걸음에 쓴 발과 마지막 걸음에 쓴 발이 서로 다르다.

무대의 모든 칸이 꺼지면 대릴의 디스코 댄스 덴이 어두워졌다고 한다.

대릴은 무용수 무리에게 이런 내기를 건다.

1. 대릴이 음악이 시작될 때 어떤 칸이 켜진 채 남고 어떤 칸이 꺼지는지 알려준다.
2. 무용수들은 몇 명이 무대에 오를지 정한다. 아무도 오르지 않아도 된다.
3. 무대에 오르는 무용수는 음악이 시작되기 전에 각자 시작 칸을 골라 그 위에 선다. 칸 위에 서 있는 것은 그 칸을 밟는 것과 다르다.
4. 무대에 오른 무용수는 각각 디스코 댄스를 한 번 춘다.
5. 무대에 오른 무용수는 한 명씩 차례로 춘다.
6. 마지막 무용수가 춤을 마치면 디스코 댄스 덴이 어두워져 있어야 한다.

예를 들어 초기 상태가 다음 그림과 같다고 하자.

이때 아래 그림 왼쪽에 표시된 칸에서 두 무용수가 시작하면 내기를 성공시킬 수 있다.

두 무용수가 춤을 마치면 켜져 있던 칸을 모두 밟았으므로 디스코 댄스 덴은 어두워진다. 두 무용수 모두 네 조건을 지켰다.

무용수들이 이 내기를 성공시킬 수 있는가? 성공시킬 수 없다면, 음악이 시작된 직후의 상태에서 켜짐과 꺼짐을 뒤집어야 하는 칸의 최소 개수는 몇 개인가?

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 테스트 케이스가 하나씩 주어진다.

각 테스트 케이스의 첫 줄에는 세 정수 $m$, $n$, $k$가 공백으로 구분되어 주어진다. 차례대로 무대의 행 개수, 열 개수, 음악이 시작될 때 불이 꺼지는 칸 묶음의 개수이다.

다음 $k$개 줄에는 네 정수 $i_0$, $j_0$, $i_1$, $j_1$이 공백으로 구분되어 주어진다. $i_0 \le i \le i_1$이고 $j_0 \le j \le j_1$인 모든 $i$, $j$에 대해 $i$행 $j$열 칸이 음악이 시작될 때 꺼진다는 뜻이다. 묶음끼리 겹칠 수 있다.

제한

• $1 \le T \le 2000$
• $1 \le m, n \le 10^5$
• $0 \le k \le 10^5$
• $1 \le i_0 \le i_1 \le m$
• $1 \le j_0 \le j_1 \le n$
• 모든 테스트 케이스의 $k$를 더한 값은 $3 \times 10^5$ 이하이다.

각 테스트 케이스마다 한 줄에 정수 $N$ 하나를 출력한다. $N$은 무용수들이 내기를 성공시킬 수 있도록 켜짐과 꺼짐을 뒤집어야 하는 칸의 최소 개수이다. 이미 성공시킬 수 있다면 $0$을 출력한다.

첫 번째 예제의 첫 테스트 케이스에서는 꺼지는 칸 묶음이 서로 겹친다. 4행 2열 칸 하나만 뒤집으면 위 그림의 무대와 똑같아지므로 답은 $1$이다.