Problem Description

度度熊最近开始迷上了一款新游戏AotD，但无奈水平太菜，被虐了很多次之后，它决定来做点什么平衡一下这款游戏。

度度熊认为自己被虐的主要原因是游戏中存在一些克制关系：比如当他玩Sniper时，就常常被Pudge虐的找不着北。所以他决定Hack这个游戏，消除一些克制关系。任意一个英雄克制与被克制的英雄个数差值越小，这个游戏就越平衡，作为“平衡大师”，度度熊的目标也是让所有英雄的这个差值的绝对值的最大值最小。

当然，完全没有克制关系，这个游戏也就失去乐趣了，所以这种关系的个数应该不低于一个值，称之为游戏乐趣值。

注意，这个克制关系是由度度熊的游戏水平决定的：比如他玩Pudge时同样会被Sniper虐，所以它也认为Sniper克制Pudge。

Input

第一行一个整数T，表示T组数据。

每组数据第一行包含三个数：英雄个数N，克制关系个数M，游戏乐趣值K。$(1 \leq N \leq 50, 0 \leq K \leq M \leq N * (N-1) )$

然后接下来的M行，每行包含两个英雄名称A和B，表示A克制B，A和B不会相同。不同名称的个数不会超过N。名称长度不超过20，且只包含字母。

度度熊很机智，在这个克制关系表中，同一个克制关系不会出现多次。

Output

对于每组数据，先输出一行

Case #i:

然后输出最小的最大差值。

2
2 2 2
Pudge Sniper
Sniper Pudge
4 4 3
Pudge Sniper
Sniper Invoker
Pudge Chen
Invoker Chen

Case #1:
0
Case #2:
1