{"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\"\u003eJo loves his teammate Ky\u0027s rick and roll! But he more than loves counting.\u003cbr\u003e\u003cbr\u003eJo thinks, for two numbers $n$ and $d$ ( $d$ is a factor of $n$ ), $d \\in Good_n$ if and only if the prime factor set of $d$ $\\textbf{equals}$ to that of $n$. That is, $Good_n\u003d\\lbrace d\\mid n\\bmod d\u003d0\\wedge \\forall p\\in Prime\\to (d\\bmod p\u003d0\\leftrightarrow n\\bmod p\u003d0)\\rbrace $.\u003cbr\u003e\u003cbr\u003eFor example, $Good_{12}\u003d\\lbrace 6, 12\\rbrace $ , since the factors of $12$ are $\\lbrace 1, 2, 3, 4, 6, 12\\rbrace $. $\\lbrace 2, 3\\rbrace $ are prime factors of $12$, so all its factors of their good factors must contain prime factors $2, 3$. Therefore, only $6, 12$ satisfy the condition.\u003cbr\u003e\u003cbr\u003eFor a number $n$, Jo will select a factor $d$ randomly from $Good_n$ with equal possibility. if $d\u003dn$, then the rich Jo will pay you $n$ yuan as reward. Otherwise, you will gain nothing.\u003cbr\u003e\u003cbr\u003eKy, the man who treats money as dirt, wants to choose an integer from $[1, M]$ randomly for Jo\u0027s game. Help Ky calculate the expectation of money he can get.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $T(T≤12)$ . Then $T$ test cases follow. \u003cbr\u003e\u003cbr\u003eFor each test case, there is only one integer $M(1\\leq M\\leq 10^{12})$.\u003cbr\u003e\u003cbr\u003eIt\u0027s guaranteed that there are at most $6$ cases such that $M\u0026gt;10^6$ ."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one integer in a single line --- the expectation of the money Ky can get.\u003cbr\u003e\u003cbr\u003eSince it can be too large, print it modulo $4179340454199820289(\u003d29\\cdot 2^{57}+1)$."}},{"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\n4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003e$Good_1\u003d\\lbrace1\\rbrace $\u003cbr\u003e\u003cbr\u003e$Good_2\u003d\\lbrace2\\rbrace $\u003cbr\u003e\u003cbr\u003e$Good_3\u003d\\lbrace3\\rbrace $\u003cbr\u003e\u003cbr\u003e$Good_4\u003d\\lbrace2, 4\\rbrace $\u003cbr\u003e\u003cbr\u003eTherefore, the answer is $\\displaystyle {1\\over 4}({1\\over |Good_1|}+{2\\over |Good_2|}+{3\\over |Good_3|}+{4\\over |Good_4|})\u003d{1\\over 4}({1\\over 1}+{2\\over 1}+{3\\over 1}+{4\\over 2})\u003d2$\u003cbr\u003e"}}]}