#2842. 魔法手镯

内存限制:256 MiB 时间限制:10 Sec

题目描述

Ginny的生日马上就来了。魔法大叔Herry准备给他的新妹子一个生日礼物。礼物是由N个魔法珠子串成的魔法手镯
。每种不同种类的珠子有其独一无二的特性。Herry的另一个妹子远坂凛指出,有一些指定种类的成对珠子,如果
挨在一块会发生化学反应甚至核聚变,因此Herry必须非常小心以确保这些珠子不会相邻。Herry想知道,究竟能有
多少不同的手镯,将这个结果mod 9973并告诉他。注意,若一个手镯能够通过旋转得到另一个手镯,我们将这两个
手镯视为相同的。

输入格式

输入包含多组数据。第一行一个正整数case,为数据的组数。接下来的数据分为case组,每一组的第一行为三个正
整数N,M,K,N为珠子的数量,M为珠子的种类数,K为不能相邻的种类对数,保证N mod 9973 != 0。接下来K行每行
两个正整数i,j,表示种类i的珠子不能和种类j的珠子相邻。

输出格式

对于每组数据,输出一行,为手镯的数量。

样例

样例输入


			
4
3 2 0
3 2 1
1 2
3 2 2
1 1
1 2
3 2 3
1 1
1 2
2 2

样例输出


			
4
2
1
0

数据范围与提示