首先 mol 一发现场 AC 的 csy 神仙
为什么这题现场这么多人过啊啊啊啊啊啊
继续搬运官方题解（
首先对于题目中的 (k,P)，我们有若存在字符串 (k,P,P’) 满足 (S=kP+P’)，且 (P’) 为 (P) 前缀，那么称 (P) 为 (S) 的一个周期，显然 (k) 最大等价于 (|P|) 最小，也就是说我们要找到对于每个 (|P|)，最短周期长度为 (|P|) 的字符串个数，那么显然对于长度为 (x) 的周期，如果一个字符串最短周期长度为 (x)，那么其对应的 (k=lfloordfrac{|S|}{n} floor)，也就是说，假设 (f(i)) 表示最短周期长度为 (i) 的字符串个数，那么
那么怎么求 (f(i)) 呢？我们不妨做以下猜想：
Observation (-1). 一个串 (S) 最小周期长度为 (x)，当且仅当长度为 (x) 的前缀是 (S) 的周期且不存在某个 (ymid x)，满足长度为 (y) 的前缀是 (S) 的周期
为什么是 (-1) 呢？因为显然这个结论是错的，反例随便举，譬如 (S=' ext{abaa}',x=3)，u1s1 我现场开场 30min 就在肝这道题并猜了这个结论，然鹅意识到这个结论是错误的，并且注意到现场 30min 没人通过这道题，感觉不对劲就放弃了（
不过注意到违背这个结论的都是 (x) 比较大的情况，对于 (x) 比较小的情况这个结论是不是就对了呢？
事实果真如此。
Observation. 一个串 (S) 最小周期长度为 (x(xlelfloordfrac{n}{2} floor))，当且仅当长度为 (x) 的前缀是 (S) 的周期且不存在某个 (ymid x)，满足长度为 (y) 的前缀是 (S) 的周期
证明：首先关于周期我们有一个周期引理（Periodicity Lemma），大概说的是如果一个字符串存在两个周期长度分别为 (x,y)，且 (x+yle n+gcd(x,y))，那么长度为 (gcd(x,y)) 的前缀也是 (S) 的周期。
这样就可以反证法了，假设存在一个 (y<x) 满足 (y mid x) 且长度为 (y) 的前缀也是 (S) 的周期，那么由于 (xlelfloordfrac{n}{2} floor)，必然有 (x+yle n<n+gcd(x,y))，套用 Periodicity Lemma 可得 (gcd(x,y)) 也是 (S) 的周期，而 (gcd(x,y)mid x)，与长度为 (x) 的前缀为 (S) 的最小周期矛盾，因此假设不成立。
注意到对于 (x>lfloordfrac{n}{2} floor)，必然有 (lfloordfrac{n}{x} floor=1)，因此
而对于 (xlelfloordfrac{n}{2} floor)，根据上面的性质有
即枚举 (S) 的前 (x) 位是什么，这样即可确定整个 (S)，同时需扣掉最小周期 (<x) 且是 (x) 的约数的串的个数。
这看起来和数论有点关系了，移个项：
也即
即
于是上面那个求答案的式子就可以整除分块+杜教筛了。时间复杂度 (Tn^{2/3})
const int MAXV=5e6;
const int MOD=998244353;
int qpow(int x,int e){
int ret=1;
for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
return ret;
}
int f[MAXV+5];
void init(){
for(int i=1,pw=2;i<=MAXV;i++,(pw<<=1)%=MOD) f[i]=pw;
for(int i=1;i<=MAXV;i++) for(int j=i<<1;j<=MAXV;j+=i) f[j]=(f[j]-f[i]+MOD)%MOD;
for(int i=1;i<=MAXV;i++) f[i]=(f[i-1]+f[i])%MOD;
}
unordered_map<int,int> sm;
int calc(int x){
if(x<=MAXV) return f[x];
if(sm.count(x)) return sm[x];int res=(qpow(2,x+1)-2+MOD)%MOD;
for(int l=2,r;l<=x;l=r+1){
r=x/(x/l);res=(res-1ll*(r-l+1)*calc(x/l)%MOD+MOD)%MOD;
} return res;
}
int main(){
init();int qu;scanf("%d",&qu);
while(qu--){
int n;scanf("%d",&n);int res=qpow(2,n);
for(int l=1,r;l<=(n>>1);l=r+1){
r=min(n/(n/l),n>>1);
res=(res+1ll*(calc(r)-calc(l-1)+MOD)*(n/l-1))%MOD;
} printf("%d
",res);
}
return 0;
}