Function

Jerry is fond of functions. He thinks the mystery of the universe is hidden behind the notations, variables and numbers.
Of all functions, he thinks $\gcd$ and $\lfloor x\rfloor$ are the most fascinating, and that something combines gcd with truncation should be even more marvelous.
Therefore, he comes up with a problem: calculate
$\sum_{i=1}^n\gcd(\lfloor{\sqrt[3]{i}}\rfloor,i)\mod 998244353$

The input contains several test cases.
The first line contains an integer $T(1\le T\le 11)$, the number of test cases.
Each of the next $T$ lines contains a integer $n(1\le n\le 10^{21})$, indicating a query.

For each test case, output one line containing an integer indicating the corresponding answer.

10
64
180
526
267
775
649
749
908
300
255

103
327
1069
522
1693
1379
1631
1998
606
492

g++ compiler on HDOJ supports __int128. And you may need the following function:

template <class T>
void read(T &x) {
  static char ch;static bool neg;
  for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
  for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
  x=neg?-x:x;
}

2019 Multi-University Training Contest 1