题目背景

你说得对，但是我不玩原神，我玩【数据删除】。

题目描述

给定正整数 $n$，求：

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\mu(ij)ij$$

其中 $\mu$ 是数论莫比乌斯函数，其定义为：

$$\mu(x) = \begin{cases}1, &x = 1,\\0,& x ~\text{存在一个大于}~1~\text{的因子是完全平方数}, \\(-1)^k, &\text{否则，其中}~k~\text{表示}~x~\text{的质因子个数}\\\end{cases} $$

答案对于 $998244353$ 取模。

输入格式

本题包含多组测试数据。

输入的第一行包含一个整数 $T$，表示测试数据的组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含一个整数 $n$。

输出格式

对于每组测试数据输出一行，包含一个整数，表示答案对 $998244353$ 取模的结果。

3
1
3
5

1
3
43

提示

• 对于 $10\%$ 的数据，满足 $1 \leq n,T \leq 100$。
• 对于 $30\%$ 的数据，满足 $1 \leq n,T \leq 5000$。
• 对于 $100\%$ 的数据，满足 $1 \leq T \leq 10^4$，$1 \leq n \leq 10^6$。