{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e金妮的生日即将到来。哈利·波特正在为他的新女朋友准备生日礼物。这份礼物是一条神奇的手链,由 \u003ci\u003en\u003c/i\u003e 颗魔法珠子组成。有 \u003ci\u003em\u003c/i\u003e 种不同的魔法珠子。每种珠子都有其独特的特点。将许多珠子串在一起就会制成一个美丽的圆形魔法手链。正如哈利·波特的朋友赫敏所指出的,某些种类的珠子会相互作用并爆炸,哈利·波特必须非常小心,以确保这些种类的珠子不会被挨着串在一起。\u003c/p\u003e\u003cp\u003e每种珠子都有无限多个。如果忽略了由手链中心旋转产生的重复,哈利能制作多少不同的手链?以模数 9973 取得答案。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含测试用例的数量。\u003c/p\u003e\u003cp\u003e每个测试用例以包含三个整数的行开始,\u003ci\u003en\u003c/i\u003e (1 ≤ \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)。接下来的 k 行每行包含两个整数 \u003ci\u003ea\u003c/i\u003e 和 \u003ci\u003eb\u003c/i\u003e (1 ≤ \u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e ≤ \u003ci\u003em\u003c/i\u003e), 表示种类为 \u003ci\u003ea\u003c/i\u003e 的珠子不能串在种类为 \u003ci\u003eb\u003c/i\u003e 的珠子旁边。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e每个测试用例的答案都输出在单独的一行上。\u003c/p\u003e"}},{"title":"示例","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"}}]}