Weird Sum

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Recently, Chef Alex invented a weird function F.
Give an integer n (n ≥ 2), consider the prime factorization n = p_{1}^{k1} · p_{2}^{k2} · … · p_{r}^{kr}.
Let g = gcd(k_{1}, k_{2}, … k_{r}) and m_{i} = k_{i} / g.
The function F is defined as: F(n) = p_{1}^{m1} · p_{2}^{m2} · … · p_{r}^{mr}.
Now, Alex is interested in summing up the value of this function for the first N natural numbers (other than 1, since its prime factorization is undefined). That is, he wants to evaluate the following expression for a given value of N: F(2) + F(3) + … + F(N).
As the above sum can be extremely large, output it modulo 998244353.
Input
The first line of the input contains an integer T denoting the number of test cases.For each test case, the only line of input contains a single integer N.
Output
For each test case, output a single line containing one integer — the above sum modulo 998244353.Subtasks
 Subtask #1: T = 10^{3}; 100 ≤ N ≤ 10^{7} (8 points)
 Subtask #2: T = 600; 100 ≤ N ≤ 10^{9} (12 points)
 Subtask #3: T = 1; 100 ≤ N ≤ 10^{18} (16 points)
 Subtask #4: T = 10^{3}; 100 ≤ N ≤ 10^{18} (18 points)
 Subtask #5: T = 1; 100 ≤ N ≤ 10^{500} (20 points)
 Subtask #6: T = 1; 100 ≤ N ≤ 10^{2016} (26 points)
Example
Input: 6 120 121 124 125 44761 31415926535897932384626433832795 Output: 6855 6866 7235 7240 2741 382417086
Explanation
Example case 2. F(121) = 11, thus the answer for this case is by eleven more than for the previous one.Example case 3. F(122) = 122; F(123) = 123; F(124) = 124, thus the answer for this case is 6866 + 122 + 123 + 124 = 7235.
Example case 4. F(125) = 5, thus the answer for this case is by five more than for the previous one.
Example case 5. Here the actual sum is 998247094 that is equal to 2741 modulo 998244353.
Example case 6. This case corresponds to the last two subtasks, where the value of N doesn't fit into 64bit integer.
Author:  alex_2oo8 
Tester:  iscsi 
Editorial  http://discuss.codechef.com/problems/WRDSUM 
Tags  alex_2oo8, biginteger, bignum, dynamicprogramming, feb16, hard, interpolation 
Date Added:  4082015 
Time Limit:  1  7 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions