Rikka with Linker

You will be familiar with the linker of C++ if you have ever compiled C++ projects in the command line. If you want to use two static libraries $liba.a$ and $libb.a$ while $liba.a$ relies on $libb.a$, you need to put $liba.a$ before $libb.a$ in your command such as $g++$ $-o$ $my$ $my.cpp$ $liba.a$ $libb.a$.

What if both $liba.a$ and $libb.a$ rely on each other? You need to add their names to the command several times such as $g++$ $-o$ $my$ $my.cpp$ $liba.a$ $libb.a$ $liba.a$. Formally, if you want to use two libraries $liba.a$ and $libb.a$ while $liba.a$ relies on $libb.a$ in your command, there must be at least one $liba.a$ which occurs before one $libb.a$.

Now, Rikka is working on her C++ project, and there are $n$ static libraries she will use. There are $m$ pairs of dependency relationships $(i, j)$ which means the $i$th project relies on the $j$th project.

You know, a complicated command will never bring happiness. So Rikka wants to simplify the compile command, i.e., Rikka wants to make the number of the names of static libraries in her compile command as small as possible. So she wants you to find out this number.

The first line contains a single integer $t(1 \leq t \leq 10^3)$, the number of the testcases.

The first line of each testcase contains two numbers $n$ and $m(1 \leq n \leq 18, 0 \leq m \leq n(n-1))$.

Then $m$ lines follow, each line contains two numbers $a$ and $b(1 \leq a,b \leq n, a \neq b)$, which describes a dependency relationship: library $a$ relies on $b$.

The input guarantees that each dependency relationship will occur at most once and there are at most $20 $ testcases with $n > 12$.

For each testcase, output a single line with a single number: the answer.

3
3 2
1 2
2 3
3 3
1 2
2 3
3 1
5 7
1 2
2 3
3 5
5 4
4 2
2 5
3 1

3
4
6