{"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\"\u003eTwo years ago, Silver187 learned Mobius inversion and knew how to calculate ($1\\le n\\le 10^9$)\u003cbr\u003e$$\\\\\\sum_{i\u003d1}^n \\sum_{j\u003d1}^n \\gcd(i,j)\\\\$$\u003cbr\u003eOne year ago, Silver187 learned how to calculate ($1\\le n\\le 10^5$)\u003cbr\u003e$$\\\\\\sum_{i\u003d1}^n \\sum_{j\u003d1}^n \\varphi(ij)\\\\$$\u003cbr\u003eBut he tried to solve this problem when $1\\le n\\le 10^9$. Finally, he failed to solve it. But he didn\u0027t completely fail, he solved a similar problem:\u003cbr\u003e\u003cbr\u003eSilver187 defines that if $n\u003d\\prod_{i\u003d1}^k p_i^{\\alpha_i}(p_i\\in \\operatorname{prime} ,\\alpha_i\\gt0, \\forall i \\ne j, p_i \\ne p_j)$ , then $H(n)\u003d\\prod_{i\u003d 1}^k p_i$. In particular, $H(1)\u003d1$.\u003cbr\u003e\u003cbr\u003eSilver187 likes gcd, so he wants to ask you to calculate the result of the following formula.\u003cbr\u003e$$\\\\(\\sum_{i\u003d1}^n \\sum_{j\u003d1}^n H(ij)[\\gcd(i,j)\u003d1])\\bmod 10^9+7\\\\$$\u003cbr\u003eNow, Silver187 asks you to solve this problem.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"First line has one integer $T(1≤T≤5)$, indicating there are $T$ test cases. In each case:\u003cbr\u003e\u003cbr\u003eOnly one line contains an integer $n(1\\le n\\le 10^9)$.\u003cbr\u003e\u003cbr\u003eInput guarantee $\\sum n\\le 2\\times 10^9$."}},{"title":"Output","value":{"format":"HTML","content":"In each case, output an integer on 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\u003e5\r\n3\r\n5\r\n1000\r\n10000\r\n1000000\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e23\r\n119\r\n181591410\r\n452132610\r\n74649566\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}