Disco Dance Debacle

Daryl owns a disco club named the Disco Dance Den. Its dance floor is an $m \times n$ grid of cells. Every cell is lit at first. When the music starts, some of the cells go unlit.

A disco dance is a sequence of at least two steps taken while the music plays. The last step of a disco dance lands on the cell the dancer started from.

A dancer steps only on lit cells. The moment he steps on a lit cell, that cell goes unlit. A dancer also obeys these four conditions:

1. The dancer alternates his left foot and his right foot from step to step. He never moves both feet at the same time.
2. Whenever he moves his left foot, it lands on a lit cell in the same column as his right foot.
3. Whenever he moves his right foot, it lands on a lit cell in the same row as his left foot.
4. The foot he uses for the first step differs from the foot he uses for the last step.

Daryl's Disco Dance Den is dark when every cell of the dance floor is unlit.

Daryl offers a dare to a group of dancers:

1. Daryl tells the dancers which cells stay lit and which cells go unlit when the music starts.
2. The dancers choose how many of them step onto the dance floor. They may send nobody.
3. The dancers on the floor pick their starting cells and stand on them before the music starts. Standing on a cell is not the same as stepping on it.
4. Each dancer on the floor performs one disco dance.
5. The dancers on the floor dance one after another.
6. After the last dancer finishes, the Disco Dance Den must be dark.

As an example, suppose the setup is this:

Two dancers can then meet the dare by starting on the cells marked on the left side of the figure below.

Once both dancers finish, the Disco Dance Den goes dark because every lit cell has been stepped on, and both dancers obeyed all four conditions.

Can the dancers meet the dare? If they cannot, what is the smallest number of cells whose state must be flipped (from lit to unlit, or from unlit to lit) right after the music starts so that the dare becomes possible?

The first line contains one integer $T$, the number of test cases. The test cases follow.

The first line of each test case contains three space separated integers $m$, $n$, and $k$: the number of rows of the grid, the number of columns of the grid, and the number of groups of cells that go unlit once the music starts.

Each of the next $k$ lines contains four space separated integers $i_0$, $j_0$, $i_1$, $j_1$. For every $i$ and $j$ with $i_0 \le i \le i_1$ and $j_0 \le j \le j_1$, the cell in row $i$ and column $j$ goes unlit when the music starts. The groups of unlit cells may overlap.

Constraints

• $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$
• The sum of $k$ over all test cases is at most $3 \times 10^5$.

For each test case print one line with a single integer $N$, the smallest number of cells whose state must be flipped so that the dancers can complete Daryl's disco dare. Print $0$ when they can already complete it.

In the first test case of the first example the groups of unlit cells overlap. Flipping one cell, the cell in row 4 and column 2, turns the floor into the grid shown in the figure above, so the answer is $1$.