{"trustable":false,"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":"MD","content":"Bowen is an avid Hearthstone $Π$ player. He likes tavern mode, and in tavern mode he likes to use Murloc, which has a followers card called Murloc Knight, the effect of this card is the battle cry which called inspire in game. As in the GIF below:\n![](https://gimg2.baidu.com/image_search/src\u003dhttp%3A%2F%2Fok.166.net%2Freunionpub%2Fds%2Fkol%2F20210909%2F170030-3cij0rgtpu.gif\u0026refer\u003dhttp%3A%2F%2Fok.166.net\u0026app\u003d2002\u0026size\u003df9999,10000\u0026q\u003da80\u0026n\u003d0\u0026g\u003d0n\u0026fmt\u003dauto?sec\u003d1663414435\u0026t\u003d52a43e1f4ab77b67db5433845634b3ad)\nAttentionly, the game rules of Hearthstone $Π$ are different from Hearthstone\u0027s rules. In Hearthstone $Π$,the length of the battlefield is $n$,player need to summon a follower for every integer position on the battlefield, and for summonning position $i$\u0027s follower ($i\\in {1, 2, 3....n-1} $),the cost is $i^4$. However,Bowen has a magic card whose effect is the position number of the followers is **NOT** coprime to $n$, and this follower‘s cost is $0$. Otherwise,the cost will not change.\nBowen starts a Hearthstone $Π$,and the length of the battlefield is $n$. Bowen wonders how much he costs after using the magic card?"}},{"title":"Input","value":{"format":"MD","content":"The first line contains an integer t indicating the number of test cases. ($1 ≤ t ≤ 1000$) Each test case, there is only one integer $n$, indicating tthe length of the battlefield. ($1 ≤ n ≤ 10^8$)\u003cbr\u003e"}},{"title":"Output","value":{"format":"MD","content":"For each test case, output an integer indicating costs after using the magic card. Because the answer is so large, please module the answer with $1,000,000,007$.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"MD","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\u003e\u003cpre\u003e2\n4\n5\n\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\u003cpre\u003e82\n354\n\n\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample Explation","value":{"format":"MD","content":"Case1: $ans\u003d1^4+3^4\u003d82$\u003cbr\u003eCase2:$ ans\u003d1^4+2^4+3^4+4^4\u003d354$\u003cbr\u003e"}},{"title":"Hits","value":{"format":"MD","content":"Coprime means $gcd\u003d1$"}}]}