很久很久以前，朕拥有着 S 国的全部领土。S 国由 个城市组成，而且某些城市有道路相连。不过，由于马车相向而行是非常危险的，所以道路都修成单向的。
朕决定在 S 国的若干不同城市设置警察局。不过由于特殊经济原因，朕只能建立恰好 个警察局。朕建立的警察局必须符合如下条件：
朕想知道一共有多少种不同的方案设置警察局（话说朕**是闲的么。。。）
每个测试点包含多组数据。
输入数据的第一行为 ，为数据个数。
每组数据的第一行为 ，代表了城市的个数、道路的个数以及建设的警察局数。以后 行，每行两个整数 ，表示有一条从 城市到 城市的道路。输入数据没有重复道路。
对每组数据输出一行，为建立 个警察局的不同方案数。
2 3 2 2 1 2 2 3 4 4 2 1 2 2 3 3 4 3 1
1
对于 的数据，，，，。
