Rectangle Tiling

There is a $2\times N$ grid with two rows and $N$ columns.

You are given $K$ rectangular regions. The $i$-th rectangle is described by four integers $x_{1,i},y_{1,i},x_{2,i},y_{2,i}$ and covers every cell whose row is between $x_{1,i}$ and $x_{2,i}$ and whose column is between $y_{1,i}$ and $y_{2,i}$, inclusive.

Choose some of the rectangles so that no two chosen rectangles cover the same grid cell.

Find the maximum possible number of chosen rectangles.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N\ K$ $x_{1,1}\ y_{1,1}\ x_{2,1}\ y_{2,1}$ $x_{1,2}\ y_{1,2}\ x_{2,2}\ y_{2,2}$ $\vdots$ $x_{1,K}\ y_{1,K}\ x_{2,K}\ y_{2,K}$

For each test case, print the maximum number of rectangles that can be selected.

• $1 \leq T \leq 200\,000$.
• $1 \leq N \leq 10^9$.
• $1 \leq K \leq 200\,000$.
• $1 \leq x_{1,i} \leq x_{2,i} \leq 2$ ($1 \leq i \leq K$).
• $1 \leq y_{1,i} \leq y_{2,i} \leq N$ ($1 \leq i \leq K$).
• The sum of $K$ over all test cases does not exceed $200\,000$.