{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eAs we know, any positive integer C ( C \u0026gt;\u003d 2 ) can be written as the multiply of some prime numbers:\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;C \u003d p1×p2× p3× ... × pk\u003cbr\u003ewhich p1, p2 ... pk are all prime numbers.For example, if C \u003d 24, then:\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;24 \u003d 2 × 2 × 2 × 3\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;here, p1 \u003d p2 \u003d p3 \u003d 2, p4 \u003d 3, k \u003d 4\u003cbr\u003e\u003cbr\u003eGiven two integers P and C. if k\u0026lt;\u003dP( k is the number of C\u0027s prime factors), we call C a lucky number of P.\u003cbr\u003e\u003cbr\u003eNow, XXX needs to count the number of pairs (a, b), which 1\u0026lt;\u003da\u0026lt;\u003dn , 1\u0026lt;\u003db\u0026lt;\u003dm, and gcd(a,b) is a lucky number of a given P ( \"gcd\" means \"greatest common divisor\").\u003cbr\u003e\u003cbr\u003ePlease note that we define 1 as lucky number of any non-negative integers because 1 has no prime factor.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of input is an integer Q meaning that there are Q test cases.\u003cbr\u003eThen Q lines follow, each line is a test case and each test case contains three non-negative numbers: n, m and P (n, m, P \u0026lt;\u003d 5×10\u003csup\u003e5\u003c/sup\u003e. Q \u0026lt;\u003d5000)."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print the number of pairs (a, b), which 1\u0026lt;\u003da\u0026lt;\u003dn , 1\u0026lt;\u003db\u0026lt;\u003dm, and gcd(a,b) is a lucky number of P."}},{"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\u003e2\r\n10 10 0\r\n10 10 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e63\r\n93\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}