RE #7 #8 #9 #10 60分求调

#include <bits/stdc++.h>
using namespace std;

const int p = 998244353, N = 10005, M = 1000005;
long long n;
long long fac[M], cnt;
long long dp[N][N];
long long pos1[M], pos2[M];

int main() {
	int T;
	cin >> T;
	while(T --) {
		cin >> n;
		cnt = 0;
		for(long long i = 1; i * i <= n; i ++) {
			if(n % i == 0) {
				fac[++ cnt] = i;
				if(i * i != n) fac[++ cnt] = n / i;
			}
		}
		sort(fac + 1, fac + cnt + 1);
		for(int i = 1; 2 * i <= cnt + 1; i ++) {
			pos1[fac[i]] = i;
			pos2[fac[i]] = cnt - i + 1;
		}
		for(int i = 1; i <= cnt; i ++) {
			if(i == 1) dp[i][1] = 1;
			else dp[i][1] = 0;
			for(int j = 2; j <= cnt; j ++) {
				dp[i][j] = dp[i][j - 1];
				if(j > i) continue;
				if(fac[i] % fac[j] == 0) {
					int tmp = fac[i] / fac[j];
					int pos = (tmp <= (int)sqrt(n) ? pos1[tmp] : pos2[n / tmp]);
					(dp[i][j] += dp[pos][j - 1]) %= p;
				}
			}
		}
		cout << dp[cnt][cnt] - 1 << endl;
	}
}