题目描述

Consider a triangle of integers, denoted by T. The value at (r, c) is denoted by Tr,c , where 1 ≤ r and 1 ≤ c ≤ r. If the greatest common divisor of r and c is exactly 1, Tr,c = c, or 0 otherwise.

Now, we have another triangle of integers, denoted by S. The value at (r, c) is denoted by S r,c , where 1 ≤ r and 1 ≤ c ≤ r. S r,c is defined as the summation    

Here comes your turn. For given positive integer k, you need to calculate the summation of elements in k-th row of the triangle S.

输入

The first line of input contains an integer t (1 ≤ t ≤ 10000) which is the number of test cases.

Each test case includes a single line with an integer k described as above satisfying 2 ≤ k ≤ 10^8 .

输出

For each case, calculate the summation of elements in the k-th row of S, and output the remainder when it divided

by 998244353.

样例输入

223

样例输出

15

所有与k不互质的数的贡献就是p1的倍数的贡献+p2的倍数的贡献+...+pu的倍数的贡献-p1*p2的倍数的贡献-p1*p3的倍数的贡献-...+p1*p2*p3的倍数的贡献+......以p1的倍数的贡献为例，他的贡献是(p1*1)^2+(p1*2)^2+...+(p1*[k/p1])^2，就是p^2*(1^2+2^2+...+(p1*[k/p1])^2

#include 
      
       #define ll long longusing namespace std;const int N=1e4+10;const int p=998244353;int T,cnt,k;bool vis[N];int prime[N],a[N];void pre(){    for (int i=2;i
       
        >=1;    }    return ret;}int fund(int n){    int sum=0;    for (int i=1;i<=cnt;i++)    {        if (prime[i]>n) break;        if (n%prime[i]==0)        {            a[sum++]=prime[i];            while (n%prime[i]==0) n/=prime[i];        }    }    if (n>1) a[sum++]=n;    return sum;}void solve(int n){    ll nn=(ll)n;    ll inv6=poww(6,p-2);    ll ans=nn%p*(nn+1)%p*(2*nn+1)%p*inv6%p;    int sum=fund(n);    ll tmp=0;    for (int i=1;i<(1<
        
         >j)&1)            {                x=x*(ll)a[j]%p;                s++;            }        }        ll t=(ll)n/x;        if (s&1) tmp=(tmp+x*x%p*t%p*(t+1)%p*(2*t+1)%p*inv6%p)%p;        else tmp=((tmp-x*x%p*t%p*(t+1)%p*(2*t+1)%p*inv6%p)%p+p)%p;    }    ans=((ans-tmp)%p+p)%p;    printf("%lld\n",ans);}int main(){    pre();    scanf("%d",&T);    while (T--)    {        scanf("%d",&k);        solve(k);    }    return 0;}