Description

Ginny’s birthday is coming soon. Harry Potter is preparing a birthday present for his new girlfrien d. The present is a magic bracelet which consists of n magic beads. The are m kinds of different mag ic beads. Each kind of beads has its unique characteristic. Stringing many beads together a beautifu l circular magic bracelet will be made. As Harry Potter’s friend Hermione has pointed out, beads of certain pairs of kinds will interact with each other and explode, Harry Potter must be very careful to make sure that beads of these pairs are not stringed next to each other.There infinite beads of each kind. How many different bracelets can Harry make if repetitions produced by rotation around th e center of the bracelet are neglected? Find the answer taken modulo 9973.

有M种不同的珠子,用它们来组成一个长度为N的项链,每种珠子个数无限. 但珠子之间存在互相讨厌的关系.问能组成多少种不同的珠子.

Format

Input

The first line of the input contains the number of test cases. Each test cases starts with a line containing three integers n (1 ≤ n ≤ 10^9, gcd(n, 9973) = 1), m (1 ≤ m ≤ 10), k (1 ≤ k ≤ m(m ? 1) ? 2). The next k lines each contain two integers a and b (1 ≤ a, b ≤ m), indicating beads of kind a cannot be stringed to beads of kind b.

输入N,M,K N代表项链长度 M代表珠子的种数. K代表有多少个互相讨厌的关系. 下面K行给出这两个互相讨厌的珠子编号.

Output

Output the answer of each test case on a separate line.

Samples

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