#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int LL; typedef pair P; typedef pair LP; const int INF=1<<30; const LL MAX=998244353; void array_show(int *array,int array_n,char middle=' '){ for(int i=0;i &vec_s,int vec_n=-1,char middle=' '){ if(vec_n==-1)vec_n=vec_s.size(); for(int i=0;i &vec_s,int vec_n=-1,char middle=' '){ if(vec_n==-1)vec_n=vec_s.size(); for(int i=0;i>=1;b>0;b>>=1){ t*=t; if(t>=p)t%=p; if(n&b)t*=a; if(t>=p)t%=p; } return t; } long long int gcd(long long int a,long long int b){ if(a=p)a%=p; if(a<0)a+=p; if(b>=p)b%=p; if(b<0)b+=p; a*=pow_mod(b,p-2,p); return a%p; } namespace sol{ bool used[1100000]; void solve(){ int n,m; LL i,j,k; LL a,b,c; cin>>n; vector pri; map m1; for(i=2;i<=n;i++){ if(used[i])continue; m1[i]=pri.size(); pri.push_back(i); for(j=i*i;j<=n;j+=i){ used[j]=true; } } vector cnt(pri.size(),0); for(i=2;i<=n;i++){ a=i; for(j=0;pri[j]*pri[j]<=i;j++){ for(k=0;a%pri[j]==0;k++,a/=pri[j]); if(k)cnt[j]=max(cnt[j],k); } if(a!=1){ b=m1[a]; cnt[b]=max(cnt[b],1LL); } } for(i=n;i>=2;i--){ if(!used[i])break; } LL s=divide(1,i,MAX); for(i=0;i