说明

自从王老板在同学面前大展身手，老师心里可开心了：哈哈哈以后的算法任务就交给这孩子了,天真的孩子哈哈哈。。。

很快，选课系统需要更新。。。

其中有个功能是这样的

每个学生需要选一门课程，很明显，学生都会选择最轻松的一门网课。天津工业大学不希望出现这样的情况，但又十分尊重学生的选择，所以给学生两个选择，然后由学校决定学生最终选哪一门课，这样就可以背后操作让学生不选最轻松的那门网课了。不过学校并没有这么做，只是希望任意一门课选择的人数最少。

是的，问题交到老师手里，老师交到王老板，王老板不屑一顾，就交给你了。(至于为什么叫这个题目，是上头的意思，我想不出有趣的题）

输入格式

第一行一个整数t，t<=10,代表t组数据。

每组数据，第一行两个整数n，m，分别代表课程数和学生数，2<=n<=100,0<=m<=1000;然后以下m行，每行两个整数a,b，代表第i个学生选择的两门课程。

输出格式

每组数据输出一个整数，占一行，代表最小化最大值。

样例

1
3 5
1 2
1 3
1 3
1 3
1 3

2

样例

1
2 3
1 2
1 2
2 1

2

提示

样例1中，第一个学生选择第二门，第二第三选择第一门，其余选第三门，最多人数为2，当然，这是还有其它最优方案。