该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有N个外形一样但重量不同的球，N是一个奇数，每个球被标号为1、2、...、N，你的任务是 找到重量在中间的那个球，我们可以通过一些比较得知某些球比其他的球要中或者轻，从而找 到一些不可能是重量处在中间的球，比如： 给定N=5个球和M=4次比较， 2比1重 4比3重 5比1重 4比2重

因为2 4 5都比1重，而1 2 3又都比4轻，从而能够判断1和4是不可能为重量处在中间的那个球。

现在请写一个程序，来找出有多少个球可以判断出不可能是中间重量的球。

Input

输入数据首先包括一个整数t，表示测试数据组数，然后是t组测试数据，每组包括一个整数N，M，然后 为M行每行两个整数a,b表示a比b重。N<=100

Output

输出能够确定不可能在中间的球的数量

Sample Input

1
5 4
2 1
4 3
5 1
4 2

Sample Output

2