问题 D: Card Game

Recently, playing card games has become popular. SPY and Markyyz are also playing a game. In this game, the cards must be placed in piles. Any number of cards can be stacked in the same pile. Any card can be placed at the bottom of an empty pile. The stacked cards go from the bottom to the top, with decreasing and consecutive values. For example, piles $(5,4,3,2,1)$, $(8,7,6,5,4,3)$, $(9)$, and $()$ (an empty pile) are all valid, while piles $(4,2,1)$ (not consecutive), $(1,2,3)$ (not decreasing), and $(9,8,7,5,6,4,3,2)$ (neither consecutive nor decreasing) are not valid. (The description of the piles mentioned above is in the order from bottom to top).

In one move, a player can choose a card from the top of a non-empty pile and move it to the top of another pile. Throughout the player's moves, the stacking rules of the cards must be followed, otherwise it is considered a foul.

SPY is now playing the card game on a table with $n$ piles, where one pile contains $k$ cards $(k,k-1,k-2,...,2,1)$, called pile 1, and the rest of the piles are empty piles. All the free slots are empty. SPY wants to move all the cards from pile 1 to another pile (pile 2). At this point, clever Markyyz comes up with a question:

Given the number of piles $n$, under the condition of not fouling, what is the maximum value of $k$ that allows the movement of $k$ cards as described above?

Since the answer could be large, take the modulus of $998244353$.

There are multiple test cases in this problem.

The first line of input contains a positive integer $t$ (1≤�≤105)(1≤t≤105), indicating the number of test cases.

Afterwards, there are $t$ test cases. Each test case consists of a single line containing an integer $n$ (2≤�≤109)(2≤n≤109), representing the number of piles.

3
2
3
114514

1
3
766171354