如果你曾经在命令行下编译过 C++ 项目，你一定对链接器很熟悉。如果你想使用两个静态库 liba.a 和 libb.a，且 liba.a 依赖于 libb.a，你需要在命令中把 liba.a 放在 libb.a 之前，例如：“g++ -o my my.cpp liba.a libb.a”。

如果 liba.a 和 libb.a 互相依赖呢？你需要多次在命令中添加它们的名字，例如：“g++ -o my my.cpp liba.a libb.a liba.a”。形式化地说，如果你想使用两个库 liba.a 和 libb.a，且 liba.a 依赖于 libb.a，那么在你的命令中，必须至少有一个 liba.a 出现在某个 libb.a 之前。

现在，Rikka 正在进行她的 C++ 项目，她将使用 $n$ 个静态库。已知有 $m$ 对依赖关系。一对 $(i, j)$ 表示第 $i$ 个库依赖于第 $j$ 个库。

你知道，复杂的命令永远不会带来快乐。因此，Rikka 想要简化编译命令。具体来说，Rikka 想要使编译命令中静态库名字的总数尽可能小。请帮她找到这个数字。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^3$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 18, 0 \le m \le n \cdot (n - 1)$)。

接下来 $m$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le n, a \neq b$)，描述一个依赖关系：库 $a$ 依赖于库 $b$。

保证每个依赖关系最多出现一次，且 $n > 12$ 的测试用例不超过 20 个。

输出格式

对于每个测试用例，输出一行，包含一个整数：Rikka 的编译命令中库名字的最少数量。

样例

输入 1

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

输出 1

3
4
6