题目描述

最近，玩卡牌游戏变得流行起来。SPY 和 Markyyz 也在玩一个游戏。在这个游戏中，卡牌必须堆成堆放置。任意数量的卡牌可以堆叠在同一个牌堆中。任何卡牌都可以放在一个空牌堆的底部。堆叠的卡牌从底部到顶部，数值必须是递减且连续的。例如，牌堆 $(5,4,3,2,1)$、$(8,7,6,5,4,3)$、$(9)$ 和空牌堆 $()$ 都是有效的，而牌堆 $(4,2,1)$（不连续）、$(1,2,3)$（非递减）以及 $(9,8,7,5,6,4,3,2)$（既不连续也非递减）则是无效的。（上述牌堆的描述顺序是从底部到顶部）。

在一次移动中，玩家可以从一个非空牌堆的顶部选择一张牌，并将其移动到另一个牌堆的顶部。在整个移动过程中，必须始终遵守卡牌的堆叠规则，否则将被视为犯规。

SPY 正在一张桌子上玩这个卡牌游戏，桌上有 $n$ 个牌堆。其中一个牌堆（称为 $1$ 号牌堆）包含 $k$ 张牌，即 $(k, k-1, k-2, \ldots, 2, 1)$，其余的牌堆都是空的。所有空闲的位置都是空的。SPY 想要将所有的牌从 $1$ 号牌堆移动到另一个牌堆（$2$ 号牌堆）。这时，聪明的 Markyyz 提出了一个问题：

给定牌堆的数量 $n$，在不犯规的条件下，能够成功移动上述的 $k$ 张牌，那么 $k$ 的最大值是多少？

由于答案可能很大，请对 $998244353$ 取模。

输入格式

本题包含多个测试用例。

输入的第一行包含一个正整数 $t$ $(1\leq t\leq 10^{5})$，表示测试用例的数量。

接下来有 $t$ 个测试用例。每个测试用例由一行组成，包含一个整数 $n$ $(2\leq n\leq 10^{9})$，表示牌堆的数量。

输出格式

对于每个测试用例，输出一行一个整数，表示牌数 $k$ 的最大值。需要对 $998244353$ 取模。

3
2
3
114514

1
3
766171354