{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eGinny\u003cspan lang\u003d\"en-us\"\u003e’s birthday is coming soon. Harry Potter is preparing a birthday present for his new girlfriend. The present is a magic bracelet which consists of \u003ci\u003en\u003c/i\u003e magic beads. The are \u003ci\u003em\u003c/i\u003e kinds of different magic beads. Each kind of beads has its unique characteristic. Stringing many beads together a beautiful circular magic bracelet will be made. As Harry Potter’\u003c/span\u003es 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.\u003c/p\u003e\u003cp\u003eThere infinite beads of each kind. How many different bracelets can Harry make if repetitions produced by rotation around the center of the bracelet are neglected? Find the answer taken modulo 9973.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains the number of test cases.\u003c/p\u003e\u003cp\u003eEach test cases starts with a line containing three integers \u003ci\u003en\u003c/i\u003e (1 \u003cspan lang\u003d\"en-us\"\u003e≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup\u003e9\u003c/sup\u003e, \u003ci\u003egcd\u003c/i\u003e(\u003ci\u003en\u003c/i\u003e, 9973) \u003d 1), \u003ci\u003em\u003c/i\u003e (1 ≤ \u003ci\u003em\u003c/i\u003e ≤ 10), \u003ci\u003ek\u003c/i\u003e (1 ≤ \u003ci\u003ek\u003c/i\u003e ≤ \u003ci\u003em\u003c/i\u003e(\u003ci\u003em\u003c/i\u003e − 1) ⁄ 2). The next k lines each contain two integers \u003ci\u003ea\u003c/i\u003e and \u003ci\u003eb\u003c/i\u003e (1 ≤ \u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e ≤\u003c/span\u003e \u003ci\u003em\u003c/i\u003e), indicating beads of kind \u003ci\u003ea\u003c/i\u003e cannot be stringed to beads of kind \u003ci\u003eb\u003c/i\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput the answer of each test case on a separate line.\u003c/p\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n3 2 0\r\n3 2 1\r\n1 2\r\n3 2 2\r\n1 1\r\n1 2\r\n3 2 3\r\n1 1\r\n1 2\r\n2 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n2\r\n1\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}