P17885 「IXOI R4」欸，云朵！？ （加强版）

IXOI Round 4 的第 4 题存在更优做法，但是由于算法超纲，没有放到比赛里，在本题可以测试更优做法。

给定一个正整数 $n$，求满足以下条件的有序整数对 $(a,b)$ 的数量： * $0\le a,b

**本题有多组数据**。 第一行输入一个正整数 $t$，表示数据组数。 接下来 $t$ 行，每行输入一个正整数 $n$，表示一组数据。

输出 $t$ 行，依次对应各组数据。 每行输出一个非负整数，表示满足条件的有序整数对数量对 $998244353$ 取模的结果。

样例一解释 当 $n=1$ 时，符合条件的有序整数对为 $(0,0),(0,1),(1,0)$，共 $3$ 个。 当 $n=2$ 时，符合条件的有序整数对为 $(0,0),(0,1),(0,2),(0,3),(1,0),(1,2),(1,3),(2,0),(2,1),(3,0),(3,1)$，共 $11$ 个。 例如，对于 $(a,b)=(1,3)$，有 $a\oplus b=2$，$a+b=4$，二者的二进制表示均恰好含有一个 $1$。 ### 数据范围 对于所有测试数据，保证 $1\le t\le10^4$，$1\le n\le10^6$。 **本题采用捆绑测试**。只有通过一个子任务中的全部测试点，才能获得该子任务的分数。各子任务没有额外的得分依赖关系。 * 子任务一（$10$ 分）：$t=1$，$n\le10$。 * 子任务二（$15$ 分）：$n\le500$。 * 子任务三（$20$ 分）：$n\le10^4$。 * 子任务四（$20$ 分）：$t=1$。 * 子任务五（$35$ 分）：无额外限制。