题目描述

SudoXue 不知道这道题能配什么图片，于是放了一只企鹅。

睡梦中，SudoXue 来到了一条长度为 $n$ 的数轴（坐标为 $1,2,\dots,n$），他在每一个整数坐标 $i$ 处放置一张卡片，其正面写着

$$f(i)=\bigl(\lfloor \sqrt{i}\rfloor^3+3\lfloor \sqrt{i}\rfloor+1\bigr)\times i -\bigl(2i+1\bigr)\times\bigl\lfloor\sqrt{i}\rfloor $$

其中 $\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数。

富有好奇心的 SudoXue 会把所有卡片依次翻开；若当前坐标 $i$ 满足

$$i\equiv\lfloor\sqrt{i}\rfloor^2\bmod (\,\lfloor\sqrt{i}\rfloor+1\,), $$

他便额外把坐标 $i$ 这一位置上所有小于等于 $\sqrt{i}$ 的正整数之和（记为 $\sigma(i)$）写在卡片背面，随后整张卡片上下叠放——也就是说，若满足条件，实际放入牌堆的数值是

$$g(i)=f(i)+\sigma(i),$$

否则仍写入 $f(i)$。

其中

$$\sigma(i)=1+2+\dots+\bigl\lfloor\sqrt{i}\bigr\rfloor $$

最后，SudoXue 计算全部牌面数字之和

$$S(n)=\sum_{i=1}^{n}g(i).$$

作为一名闲得没事干的学生，你需要帮助他快速输出 $S(n)\bmod 998\,244\,353$。

输入格式

第一行一个整数 $T$，表示测试组数。 接下来 $T$ 行，每行一个整数 $n$。

输出格式

对于每组测试数据，输出一行一个整数，表示 $S(n)\bmod 998\,244\,353$。

3
1
10
1000000000000000000

3
932
188665635

数据规模与约定

子任务	分数占比	约束
$1$	$20\%$	$n\le 10^{6}$
$2$	$80\%$	$n\le 10^{18}$

对于 $100\%$ 的数据，$1\le T\le 10^{5}$。