题目描述

小明画了一个 $n$ 个点的完全图。

他想选若干个点（不会是 $0$ 个或 $1$ 个），设选了 $m$ 个点，选的点用边连起来，总共连 $m$ 条边。这 $m$ 条边会形成一个环，已知他选一个点的概率为 $\dfrac{1}{2}$，求连成的环为奇环的概率。答案对 $998244353$ 取模。

输入格式

多组数据。

第一行整数 $T$，为数据的组数。

接下来 $T$ 行，每行一个整数 $n$。

输出格式

共 $T$ 行，每行为该组数据的答案。

样例 #1

样例输入 #1

3
3
4
5

样例输出 #1

748683265
90749487
38394014

提示

$1\le T\le1000,3\le n\le10^7$。