{"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\"\u003eZhu and 772002 are both good at math. One day, Zhu wants to test the ability of 772002, so he asks 772002 to solve a math problem. \u003cbr\u003e\u003cbr\u003eBut 772002 has a appointment with his girl friend. So 772002 gives this problem to you.\u003cbr\u003e\u003cbr\u003eThere are $n$ numbers $a_1, a_2, ..., a_n$. The value of the prime factors of each number does not exceed $2000$, you can choose at least one number and multiply them, then you can get a number $b$.\u003cbr\u003e\u003cbr\u003e How many different ways of choices can make $b$ is a perfect square number. The answer maybe too large, so you should output the answer modulo by $1000000007$.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"First line is a positive integer $T$ , represents there are $T$ test cases.\u003cbr\u003e\u003cbr\u003eFor each test case:\u003cbr\u003e\u003cbr\u003eFirst line includes a number $n(1 \\leq n \\leq 300)$,next line there are $n$ numbers $a_1, a_2, ..., a_n, (1 \\leq a_i \\leq 10^{18})$."}},{"title":"Output","value":{"format":"HTML","content":"For the i-th test case , first output Case #i: in a single line.\u003cbr\u003e\u003cbr\u003eThen output the answer of i-th test case modulo by $1000000007$."}},{"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\n3\r\n3 3 4\r\n3\r\n2 2 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1:\r\n3\r\nCase #2:\r\n3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}