首先能注意到最终序列最大值一定在两端，这样可以递归为子问题，并且把每一步的最大值拎出来之后的序列一定是一个前缀 gcd 递减的序列，因此应该可以设 $f_{i,x}$ 表示当前要求 max=i，前缀 gcd=x 的方案数，转移即为 $f_{j,x} \times 2 \times [\gcd(i,x)\neq x] \to f_{i,\gcd(i,x)}$。这个应该是对的，至少样例测着没问题。

然后考虑枚举一个 $i$ 的因子，钦定它是 $\gcd$，算出方案数，这个是好算的，做一次类似于狄利克雷前缀和的东西。算完之后容斥就是从大到小枚举每个因子，再枚举这个因子的因子，然后给因子的因子减掉自己的答案。

然后它寄了，反正没过样例，经测试如果我前面那个暴力 dp 是对的话，在 $n=6$ 的时候就寄了，答案是 60 它算出来 64。输出了一下是 $f_{2,1}$ 算错了，然后就懵了。

代码在下面。

#include<bits/stdc++.h>
#define ri register int
#define ll long long
#define mkp make_pair
#define ld long double
#define mkt make_tuple
using namespace std;
const int inf=1e9;
const int maxn=1e6+7;
const int mod=998244353;
int n;
unordered_map<int,ll>f[maxn];
vector<int>d[maxn];
ll sum[maxn];
void solve(){
	cin>>n;
	for(ri i=1;i<=n;i++)f[i].clear(),d[i].clear();
	for(ri i=1;i<=n;i++)sum[i]=0;
	for(ri i=1;i<=n;i++){
		for(ri j=i;j<=n;j+=i)d[j].emplace_back(i);
	}
	for(ri i=n;i;i--){
		for(auto x:d[i])f[i][x]=sum[x]*2%mod;
		for(ri j=d[i].size()-1;j>=0;j--){
			for(auto x:d[d[i][j]]){
				if(x!=d[i][j])f[i][x]=(f[i][x]-f[i][d[i][j]]+mod)%mod;
			}
		}
		f[i][i]++;
		for(auto x:d[i])for(auto xx:d[x])if(xx!=x)sum[xx]=(sum[xx]+f[i][x])%mod;
	}
	ll ans=0;
	for(ri i=1;i<=n;i++){
		for(auto x:d[i]){
			ans=(ans+f[i][x])%mod;
		}
	}
	cout<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(0);
	int T;cin>>T;while(T--)solve();
	return 0;
}
/*
5
7 10
2 3
6 4
1 6
4 1
*/