{"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\"\u003eThere are n people standing in a line. Each of them has a unique id number.\u003cbr\u003e\u003cbr\u003eNow the Ragnarok is coming. We should choose 3 people to defend the evil. As a group, the 3 people should be able to communicate. They are able to communicate if and only if their id numbers are pairwise coprime or pairwise not coprime. In other words, if their id numbers are a, b, c, then they can communicate if and only if [(a, b) \u003d (b, c) \u003d (a, c) \u003d 1] or [(a, b) ≠ 1 and (a, c) ≠ 1 and (b, c) ≠ 1], where (x, y) denotes the greatest common divisor of x and y.\u003cbr\u003e\u003cbr\u003eWe want to know how many 3-people-groups can be chosen from the n people.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer T (T ≤ 5), denoting the number of the test cases.\u003cbr\u003e\u003cbr\u003eFor each test case, the first line contains an integer n(3 ≤ n ≤ 10\u003csup\u003e5\u003c/sup\u003e), denoting the number of people. The next line contains n distinct integers a\u003csub\u003e1\u003c/sub\u003e, a\u003csub\u003e2\u003c/sub\u003e, . . . , a\u003csub\u003en\u003c/sub\u003e(1 ≤ a\u003csub\u003ei\u003c/sub\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e) separated by a single space, where a\u003csub\u003ei\u003c/sub\u003e stands for the id number of the i-th person."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output the answer in a line."}},{"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\u003e1\r\n5\r\n1 3 9 10 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}