小苯的因子查询
题号：NC293339
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小苯对奇数很感兴趣，他给定了一个正整数 n，希望你求出：如果从 n!（即 n 的阶乘）的因子中随机等概地取一个数，则其是奇数的概率是多少，请你帮他算一算吧。
\hspace{15pt}x 的因子：即整除 x 的正整数，例如 3 就是 6 的因子，2 也是。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\ (1\leqq T\leqq 2 \times 10^5) 代表数据组数。
\hspace{15pt}接下来一行输入 T 个由空格分割的正整数 n\ (1 \leqq n \leqq 10^6)，表示小苯当前询问的 n。

输出描述:

对于每组测试数据：
\hspace{15pt}在单独的一行输出 T 个正整数，表示对小苯每次询问的回答。
（可以证明答案是一个不可约分数 \frac{p}{q}。为了避免精度问题，请直接输出整数 p\cdot q^{-1}\ \rm mod\ M 作为答案，其中 M=998244353，q^{-1} 是满足 的 p\times q^{-1} \equiv 1 \ \rm mod\ M 整数。)
示例1

输入

复制 
10
1 2 3 4 5 6 7 8 9 10

输出

复制 
1 499122177 499122177 748683265 748683265 598946612 598946612 873463809 873463809 443664157

说明

以第三组 n=3 的测试数据为例，3!=6，而 6 的因子有：\{1,2,3,6\}，从中任选一个数字为奇数的概率为 \frac{1}{2}，对 998244353 取模的值为 499122177。