CF1924C.Fractal Origami

You have a square piece of paper with a side length equal to $1$ unit. In one operation, you fold each corner of the square to the center of the paper, thus forming another square with a side length equal to $\dfrac{1}{\sqrt{2}}$ units. By taking this square as a new square, you do the operation again and repeat this process a total of $N$ times.

Performing operations for $N = 2$.

After performing the set of operations, you open the paper with the same side up you started with and see some crease lines on it. Every crease line is one of two types: a mountain or a valley. A mountain is when the paper folds outward, and a valley is when the paper folds inward.

You calculate the sum of the length of all mountain crease lines on the paper and call it $M$. Similarly, you calculate for valley crease lines and call it $V$. You want to find the value of $\dfrac{M}{V}$.

It can be proved that this value can be represented in the form of $A + B\sqrt{2}$, where $A$ and $B$ are rational numbers. Let this $B$ be represented as an irreducible fraction $\dfrac{p}{q}$, your task is to print $p*inv(q)$ modulo $999\,999\,893$ (note the unusual modulo), where $inv(q)$ is the modular inverse of $q$.

你有一张边长为 $1$ 单位的正方形纸片。每次操作中，你将正方形的每个角都向纸片中心折叠，从而形成一个新的正方形，其边长为 $\dfrac{1}{\sqrt{2}}$ 单位。将这个新正方形视为当前正方形，重复上述操作，共进行 $N$ 次。

对 $N = 2$ 执行操作的示意图。

完成全部操作后，你将纸片沿初始朝上的同一面展开，此时纸面上会留下若干折痕线。每条折痕线属于两种类型之一：山折线（mountain）或谷折线（valley）。山折线指纸张向外折叠形成的折痕，谷折线指纸张向内折叠形成的折痕。

你计算纸面上所有山折线的总长度，记为 $M$；类似地，计算所有谷折线的总长度，记为 $V$。你需要求出比值 $\dfrac{M}{V}$。

可以证明该比值可表示为 $A + B\sqrt{2}$ 的形式，其中 $A$ 和 $B$ 均为有理数。设该 $B$ 表示为既约分数 $\dfrac{p}{q}$，你的任务是输出 $p \times inv(q) \bmod 999\,999\,893$（注意此处模数非常规），其中 $inv(q)$ 是 $q$ 关于模 $999\,999\,893$ 的模逆元。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). Description of the test cases follows.

The only line of each test case contains an integer $N$ ($1 \leq N \leq 10^9$), the number of operations you perform on the square paper.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 10^4$）。随后是测试用例的描述。

每个测试用例仅有一行，包含一个整数 $N$（$1 \leq N \leq 10^9$），表示你在正方形纸上执行的操作次数。

For each test case, print on a new line the required answer.

对于每个测试用例，在新的一行上输出所要求的答案。

The blue lines in the given figures represent mountain crease lines, and the green lines represent valley crease lines.

Crease lines after $1$ operation $(\dfrac{M}{V} = 0)$.

Crease lines after $2$ operations $(\dfrac{M}{V} = \sqrt{2} - 1)$.

图中蓝色线条表示山折线，绿色线条表示谷折线。

经过 $1$ 次操作后的折痕线 $\left(\dfrac{M}{V} = 0\right)$。

经过 $2$ 次操作后的折痕线 $\left(\dfrac{M}{V} = \sqrt{2} - 1\right)$。