Mog Scheduling

Mog shares a room in Uzbekistan with $N-1$ other participants. Initially, all $N$ people are inside the room.

The room has exactly one key, initially inside the room. The door locks automatically whenever it closes. Opening it from outside requires the key, but a person inside can open it for someone outside.

When leaving, a person may take the key or leave it inside. The key cannot be passed to someone who is already outside.

Each person has at least one outing schedule. A schedule $(p,l,r)$ means that person $p$ leaves at time $l$ and returns at time $r$. Schedules belonging to the same person do not overlap. All starting and ending times across all schedules are distinct.

Mog chooses a subset of the schedules. Only the chosen schedules are performed; an unchosen schedule does not cause its owner to leave.

If someone returns while nobody is inside and they do not have the key, that person must wait outside.

Find the maximum number of schedules that can be chosen such that an appropriate handling of the key ensures that nobody ever has to wait.

The input is given in the following format:

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

For each test case, print the maximum possible number of selected outing schedules on one line.

• $1 \le T \le 10\,000$.
• $1 \le N \le M \le 200\,000$.