说明

500次啊，500次啊~

小东东一默念着一边想着“到底要不要发微博了呢？”自从出台了有关微博转发500次就要...

哎！这正是现在小东东苦恼的事情。小东东想着有那么多的死党关注了自己，而且每个死党还有很多粉丝。如果每个死党和他的粉丝们都转发一次自己的微博，500次以后估计什么也都说不清了。现在他决定一个一个的查看过去，看看自己的一条微博到底会被转发多少次。可是想想自己死党那么多，他又懒的不想动于是把这个任务交给你了，现在请你用程序帮帮他的忙。

输入格式

第一行一个整数T表示有T组测试数据（T<=20），接下来的一行包含两个整数N和ID，N表示接下来有N个关系（N<=100000），ID是小东东的微博编号。

紧接着的N行每行两个整数A和B，表示编号为A的同学关注了编号为B的同学（也就是A是B的粉丝）。

每个人微博的编号在[1,10000]内。

输出格式

请根据上述的粉丝关系，计算小东东的一条微博最多会被转发多少次。（请注意输出格式，输出的冒号后有一个空格）

样例

2
14 1
2 1
3 1
4 1
6 1
3 2
4 2
3 4
3 5
4 5
6 5
4 6
5 6
4 7
6 7
4 4
1 2
2 3
3 4
4 1

Case #1: 5
Case #2: 3

提示

如果A关注了B（A是B的粉丝），那么B发送的每条微博A都会转发，相同的微博每个人只发一次。