题目描述

一个城镇由 $\red {N }$个交叉口和 $\red {M }$个单向道路组成，每条道路从一个交叉口通向另一个交叉口。

从任何一个交叉口出发，经过城镇的街道都无法回到出发的交叉口，即城镇的街道无法形成一个循环。

现在要选择一些交叉口空降士兵，士兵可以沿着街道一直走到尽头。

要求空降士兵走遍所有的交叉口，并且每个交叉口只能被一个士兵走一次。

请问最少需要多少名士兵。

输入格式

第一行包含整数 $\red {T}$，表示共有 $\red {T }$组测试数据。

每组测试数据第一行包含整数 $\red {N}$，第二行包含整数 $\red {M}$。

接下来 $\red {M}$ 行，每行包含两个整数$\red { X}$ 和 $\red {Y}$，表示存在一条道路从交叉口 $\red {X}$ 通向交叉口$\red { Y}$。

输出格式

每组数据输出一个整数，表示需要的最少士兵数目。

每个结果占一行。

样例

输入样例

2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3

输出样例

2
1

提示

$\red {0<N≤120}$,

$\red {1≤X,Y≤N}$