Evacuation

Most of the ants working in the CC garden died in a sudden disaster, and only 1000 queen ants and a few worker ants survived. To keep the colony alive, the survivors decided to send some of the queens to a shelter. The shelter is very safe, and in a few months the colony will grow there again.

The shelter is laid out like this.

1. The shelter has $N$ checkpoints and $M$ roads that join checkpoints.
2. If $x < y$, checkpoint $x$ sits at a higher altitude than checkpoint $y$.
3. A road always runs from the higher checkpoint to the lower one.
4. An ant cannot move from a lower checkpoint to a higher one.
5. Each road that touches checkpoint $1$ carries only one ant.
6. Each road that touches checkpoint $N$ carries only one ant.
7. At most one road directly joins two checkpoints $u$ and $v$.

A road that touches neither checkpoint $1$ nor checkpoint $N$ has no limit on how many ants use it, and a checkpoint has no limit on how many ants stay there.

Every queen ant starts at checkpoint $1$. A queen that never reaches checkpoint $N$ does not survive, so the ants want to send as many queens as possible to checkpoint $N$. The remaining queens join the defense line.

Find the largest number of queen ants that can reach the shelter.

The first line has the number of test cases $T$.

The first line of each test case has the number of checkpoints $N$ ($2 \le N \le 200$) and the number of roads $M$ ($1 \le M \le N(N-1)/2$).

Each of the next $M$ lines has two integers $x$, $y$ ($1 \le x < y \le N$), meaning a road runs from checkpoint $x$ to checkpoint $y$.

For each test case, print on one line the largest number of queen ants that can reach checkpoint $N$.