Background

tq是一名赛蛆，近日在巅峰中苦受华猎和大姐猪组合的困扰，听说圣谕之风·岚可以有效的打击这两个组合，所以决定去打一只，但是要获得圣谕之风·岚必须要先获得他的先制风之子岚，由于关卡非常恶心，他想知道期望的操作次数你能帮帮他吗？

Description

你要通过一个点灯游戏，一共有 $T$ 次独立的挑战。每次挑战给出一个整数 $n$，表示该次挑战一共有 $n$ 盏灯。

初始状态下所有灯均为关闭状态。你每次等概率地随机点亮其中一盏灯：

如果这盏灯此前未被点亮，它将被点亮，你离通关更进一步；

如果这盏灯已经被点亮过，则 所有灯都会熄灭，你必须从该关的初始状态重新开始。

请你计算，通过 $n$ 盏灯所需的期望操作次数之和，并对 $998244353$ 取模输出。

Format

Input

第一行一个整数 $T$（$1 \le T \le 10^5$），表示测试数据组数。

接下来 $T$ 行，每行一个整数 $n$（$1 \le n \le 10^6$），表示某一关的灯数。 数据保证所有 $n$ 的和不超过 $10^6$

Output

对于每次询问: 输出一行一个整数，表示所有关卡期望操作次数之和对 $998244353$ 取模的结果。

Samples

3
1
2
3

1
4
12