我们会活下去。我们会痊愈。伤疤……我们会留着。为了不忘记。——阿米西亚

Nous vivrons. Et nous guérirons. Les cicatrices... Nous les gardons. Pour ne pas oublier. - Amicia

在与老鼠进行了一场压倒性的战斗后，阿米西亚（Amicia）和雨果（Hugo）是时候逃离阿尔勒的维克多伯爵（Count Victor de Arles）的军队了。士兵们驻扎在一条狭窄的通道上，这条通道可以用一个大小为 $2 \times n$ 的矩阵来表示。此外，我们知道这条通道上总共有 $k$ 个士兵。

阿米西亚和雨果将某种配置的“危险度”定义为其中士兵连通块（组）的数量。更正式地，考虑一个 $2 \times n$ 的 01 矩阵，其中有士兵的位置的值为 $1$。如果两个单元格的值均为 $1$ 且它们共享一条边，则称这两个单元格是连通的。注意，这种关系具有传递性，即如果单元格 $a$ 和 $b$ 连通，且单元格 $b$ 和 $c$ 连通，则 $a$ 和 $c$ 也被视为连通。一个连通块是值为 $1$ 的连通单元格的极大子集。危险度就是该矩阵中连通块的数量。

你的任务是帮助两位主角求出在考虑所有可能配置的情况下，危险度的期望值。每种配置出现的概率均等。在这种情况下，期望值可以定义为所有可能配置中连通块数量的平均值。

实现细节

你必须实现以下函数：

void prec(int subtask_id)

int solve(int n, int k)

第一个函数将在评测程序（grader）开始时被调用一次。你可以用它来进行预处理。

第二个函数应当在给定参数 $n$ 和 $k$ 的情况下，返回期望的危险度模 $998\,244\,353$ 的值。正式地，设 $M = 998\,244\,353$。可以证明答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod M$。返回等于 $p \cdot q^{-1} \pmod M$ 的整数。换句话说，返回一个满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod M$ 的整数 $x$。

第二个函数将被调用 $t$ 次。这意味着输入中包含多个测试用例！

请不要忘记包含头文件 kor.h，否则会导致编译错误！

数据范围

• $1 \le t \le 10$
• $1 \le n \le 10^9$
• $0 \le k \le 10^6$
• $k \le 2 \cdot n$

样例

样例输入 1

2
6
2 2
5 10
2000 3
2000 5
100 32
150 278

样例输出 1

332748119
1
518205646
742082393
368118258
937239298

样例说明 1

注意，评测程序（grader）的输入包含测试的子任务编号、测试用例数量 $t$ 以及每个测试用例的 $n, k$。

对于第一个测试用例（$n=2, k=2$），所有可能的配置如下图所示：

总共有 6 种配置，其中 4 种只有一个连通块，另外 2 种有两个连通块。 因此，期望值为 $\frac{4 \cdot 1 + 2 \cdot 2}{6} = \frac{8}{6} = \frac{4}{3}$。 在模 $998\,244\,353$ 意义下，$\frac{4}{3} \equiv 332748119 \pmod{998\,244\,353}$。

样例输入 2

7
8
100000000 0
100000000 1
100000000 2
100000000 3
5219873 192
853875838 238
43782384 1500
58123292 180000

样例输出 2

0
1
268791198
806373591
782159797
435727907
712321002
257644694