Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

I. Evolutionary Pathways
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Medha is a researcher who is investigating a certain species of monkeys. These species have two characteristics of interest to researchers: a fitness score (represented by a positive integer) and a special OP gene. The OP gene has the property that at any given time, it is present in exactly one species of monkeys.

At the beginning of every epoch, a new species of monkey evolves and branches off from each existing species, but the original species also continues to exist. The only exception is the species that currently contains the OP gene, in which case a new species may or may not evolve from it.

Let's call the new species the child and the species it evolved from the parent. Since evolution is very effective at producing beneficial adaptations, the child species will always have a higher fitness score than its parent species.

In the present day, there are $$$n$$$ different species of monkeys where the $$$i$$$-th species has a fitness score of $$$i$$$. It is known that all species evolved at exactly one time in history and evolved from one parent species. Species $$$1$$$ is an ancestor of all other species.

Count the number of distinct evolutionary pathways modulo $$$998244353$$$. Two pathways are distinct if there are two species with the same fitness score that evolved from different parent species.

Input

The first line of the input will contain an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$), the number of test cases.

The next $$$t$$$ lines of the input will each contain an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).

Note that there is no constraint on the sum of $$$n$$$ over all test cases.

Output

Print $$$t$$$ lines, the number of distinct evolutionary pathways for each testcase. Make sure to print your answer modulo $$$998244353$$$.

Example
Input
3
2
3
100000
Output
1
3
725526327
Note

For the case when $$$n=3$$$, there are $$$3$$$ possibilities.

  • First, species $$$2$$$ evolved from species $$$1$$$ and also inherited the special gene. Then, species $$$3$$$ evolved from species $$$1$$$ while no new species evolved from species $$$2$$$.
  • First, species $$$3$$$ evolved from species $$$1$$$ and also inherited the special gene. Then, species $$$2$$$ evolved from species $$$1$$$ while no new species evolved from species $$$3$$$.
  • First, species $$$2$$$ evolved from species $$$1$$$ but $$$1$$$ retained the special gene. Then, species $$$3$$$ evolved from species $$$2$$$ while no new species evolved from species $$$1$$$.

Note that the following situation is impossible.

  • First, species $$$3$$$ evolved from species $$$1$$$ but $$$1$$$ retained the special gene. Then, species $$$2$$$ evolved from species $$$3$$$ while no new species evolved from species $$$1$$$.

This is because of the constraint that the child species will always have a higher fitness score than its parent species.