Recently, playing card games has become popular. BLUE and ACMZYX 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.

BLUE 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. BLUE wants to move all the cards from pile 1 to another pile (pile 2). At this point, clever ACMZYX 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 ≤ t ≤ 10⁵ ), 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 ≤ n ≤ 10⁹ ), representing the number of piles. 

For each test case, output a single line containing an integer, representing the maximum value of k for the number of cards. Take the modulus of 998244353

 2023“钉耙编程”中国大学生算法设计超级联赛（2）